Line data Source code
1 : /* Symbolic vectors of bits e.g. "(buf_a[0-10) + buf_b[0-len) + (0b * 8))"
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "analyzer/common.h"
22 :
23 : #include "gimple-pretty-print.h"
24 : #include "fold-const.h"
25 : #include "tm.h"
26 :
27 : #include "diagnostics/markup.h"
28 : #include "selftest.h"
29 :
30 : #include "analyzer/symbolic-bit-vectors.h"
31 : #include "analyzer/region-model.h"
32 : #include "analyzer/liveness-context.h"
33 : #include "analyzer/analyzer-selftests.h"
34 :
35 : #if ENABLE_ANALYZER
36 :
37 : namespace ana {
38 :
39 : // TODO: move this
40 : /* class conjured_purge. */
41 :
42 : /* Purge state relating to BV. */
43 :
44 : void
45 11572 : conjured_purge::purge (const symbolic::conjured_bit_vector &bv) const
46 : {
47 11572 : m_model->purge_state_involving (bv, m_ctxt);
48 11572 : }
49 :
50 : /* Purge state relating to BV. */
51 :
52 : void
53 13321 : conjured_purge::purge (const symbolic::conjured_bit_contents &bc) const
54 : {
55 13321 : m_model->purge_state_involving (bc, m_ctxt);
56 13321 : }
57 :
58 : namespace symbolic {
59 :
60 : // class bit_vector : public symbolic::node
61 :
62 1257080 : bit_vector::bit_vector (bit_vector_manager &bv_mgr,
63 : complexity c,
64 : const symbolic_bit_size &size_in_bits)
65 1257080 : : value_node (c, bv_mgr.get_node_manager ().alloc_node_id ()),
66 1257080 : m_bv_mgr (bv_mgr),
67 1257080 : m_size_in_bits (size_in_bits)
68 : {
69 1257080 : }
70 :
71 : void
72 2754 : bit_vector::print_dump_widget_label (pretty_printer *pp) const
73 : {
74 2754 : start_any_dump_color (pp);
75 :
76 2754 : print_prefix_for_dump_widget_label (pp);
77 :
78 2754 : pp_string (pp, "[size: ");
79 :
80 2754 : end_any_dump_color (pp);
81 2754 : m_size_in_bits.start_any_dump_color (pp);
82 :
83 2754 : m_size_in_bits.dump_inline_to_pp (pp, units::role::size);
84 :
85 2754 : m_size_in_bits.end_any_dump_color (pp);
86 2754 : start_any_dump_color (pp);
87 :
88 2754 : pp_string (pp, "]");
89 :
90 2754 : print_any_suffix_for_dump_widget_label (pp);
91 :
92 2754 : end_any_dump_color (pp);
93 2754 : }
94 :
95 : bool
96 0 : bit_vector::maybe_print_for_user (pretty_printer *,
97 : const region_model &,
98 : const symbolic::node *) const
99 : {
100 0 : return false;
101 : }
102 :
103 : const symbolic_byte_size *
104 106 : bit_vector::maybe_get_size_in_bytes () const
105 : {
106 106 : return maybe_bytes_from_bits (m_size_in_bits);
107 : }
108 :
109 : bool
110 870480 : bit_vector::maybe_get_concrete_size_in_bits (concrete_bit_size *out) const
111 : {
112 870480 : return concrete_from_symbolic (m_size_in_bits, out);
113 : }
114 :
115 : bool
116 747482 : bit_vector::maybe_get_concrete_size_in_bytes (concrete_byte_size *out) const
117 : {
118 747482 : concrete_bit_size conc_bit_size;
119 747482 : if (!maybe_get_concrete_size_in_bits (&conc_bit_size))
120 : return false;
121 736326 : return maybe_bytes_from_bits (conc_bit_size, out);
122 747482 : }
123 :
124 : /* Base implementation of get_tristate_at_offset: crop to one bit, and get
125 : that bit as a tristate. */
126 :
127 : tristate
128 832 : bit_vector::get_tristate_at_offset (const symbolic_bit_offset &bit) const
129 : {
130 832 : auto &bit_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bits ();
131 832 : auto &bv_for_bit = get_cropped_bits
132 832 : (symbolic_bit_range (bit,
133 832 : bit_mgr.get_concrete (1_bit)));
134 832 : gcc_assert (bv_for_bit.get_size ().is_one_p ());
135 832 : auto *ts_bv = bv_for_bit.dyn_cast_tristate_bit_vector ();
136 832 : if (!ts_bv)
137 24 : return tristate::unknown ();
138 808 : return ts_bv->get_bit_value ();
139 : }
140 :
141 : class hexdumper
142 : {
143 : public:
144 56 : hexdumper (text_art::style_manager &sm,
145 : const hexdump_options &hexdump_opts)
146 56 : : m_sm (sm),
147 56 : m_hexdump_opts (hexdump_opts),
148 56 : m_num_columns (1),
149 56 : m_x_bit_range (0),
150 56 : m_x_binary (-1),
151 56 : m_x_hex (-1),
152 56 : m_x_ascii (-1)
153 : {
154 56 : if (hexdump_opts.m_show_binary)
155 36 : m_x_binary = m_num_columns++;
156 56 : if (hexdump_opts.m_show_hex)
157 52 : m_x_hex = m_num_columns++;
158 56 : if (hexdump_opts.m_show_ascii)
159 36 : m_x_ascii = m_num_columns++;
160 56 : }
161 :
162 : text_art::table
163 56 : make_table (const bit_vector &bv,
164 : concrete_bit_size conc_bit_size)
165 : {
166 56 : using namespace text_art;
167 :
168 56 : auto bits_per_line = bits_from_bytes (m_hexdump_opts.m_bytes_per_line);
169 :
170 56 : table t (table::size_t (m_num_columns, 0));
171 :
172 56 : if (m_hexdump_opts.m_show_headings)
173 : {
174 4 : int y_headings = t.add_row ();
175 4 : if (m_x_binary >= 0)
176 4 : t.set_cell (table::coord_t (m_x_binary, y_headings),
177 8 : styled_string (m_sm, "Binary"));
178 4 : if (m_x_hex >= 0)
179 4 : t.set_cell (table::coord_t (m_x_hex, y_headings),
180 8 : styled_string (m_sm, "Hex"));
181 4 : if (m_x_ascii >= 0)
182 4 : t.set_cell (table::coord_t (m_x_ascii, y_headings),
183 8 : styled_string (m_sm, "ASCII"));
184 : }
185 :
186 56 : for (concrete_bit_offset start_of_this_line = 0_bits;
187 148 : start_of_this_line < conc_bit_size;
188 92 : start_of_this_line += bits_per_line)
189 : {
190 92 : auto start_of_next_line = start_of_this_line + bits_per_line;
191 92 : auto size_of_this_line = (start_of_next_line < conc_bit_size
192 92 : ? bits_per_line
193 92 : : conc_bit_size - start_of_this_line);
194 184 : add_hexdump_line (t,
195 : bv,
196 92 : concrete_bit_range (start_of_this_line,
197 276 : size_of_this_line));
198 92 : }
199 56 : return t;
200 56 : }
201 :
202 : private:
203 : void
204 92 : add_hexdump_line (text_art::table &t,
205 : const bit_vector &bv,
206 : concrete_bit_range bits_on_line)
207 : {
208 92 : using namespace text_art;
209 :
210 184 : gcc_assert (bits_on_line.get_start_offset () >= 0_bits);
211 : //gcc_assert (bits_on_line.get_last_offset () < bv.get_size ());
212 :
213 92 : auto row_y = t.add_row ();
214 :
215 92 : {
216 92 : pretty_printer pp;
217 92 : bits_on_line.dump_to_pp_pretty (&pp);
218 92 : t.set_cell (table::coord_t (0, row_y),
219 184 : styled_string (m_sm, pp_formatted_text (&pp)),
220 : x_align::RIGHT);
221 92 : }
222 :
223 : /* Try to print the individual bits. */
224 92 : if (m_x_binary >= 0)
225 : {
226 60 : pretty_printer pp;
227 60 : int count = 0;
228 60 : for (concrete_bit_offset i = bits_on_line.get_start_offset ();
229 1872 : i < bits_on_line.get_next_offset ();
230 1812 : i += 1_bit, ++count)
231 : {
232 1812 : tristate ts = bv.get_tristate_at_offset (i);
233 1812 : pp_character (&pp, get_dump_char_for_tristate_bit (ts));
234 :
235 : // Add a space every 8 bits:
236 3624 : if (count % 8 == 7
237 2036 : && i < bits_on_line.get_last_offset ())
238 168 : pp_space (&pp);
239 60 : }
240 60 : t.set_cell (table::coord_t (m_x_binary, row_y),
241 120 : styled_string (m_sm, pp_formatted_text (&pp)),
242 : x_align::LEFT);
243 60 : }
244 :
245 : /* Try to print individual bytes. */
246 92 : if (m_x_hex >= 0)
247 : {
248 88 : pretty_printer pp;
249 88 : bool first = true;
250 496 : for (concrete_bit_offset i = bits_on_line.get_start_offset ();
251 496 : i < bits_on_line.get_next_offset ();
252 408 : i += 8_bits)
253 : {
254 408 : if (i + 7_bits < bits_on_line.get_next_offset ())
255 : {
256 408 : auto &byte
257 1224 : = bv.get_cropped_bits (concrete_bit_range (i, 8_bits));
258 408 : uint8_t byte_val;
259 408 : if (first)
260 : first = false;
261 : else
262 320 : pp_space (&pp);
263 408 : if (byte.maybe_as_uint8 (&byte_val))
264 376 : print_byte_as_hex (&pp, byte_val);
265 : else
266 32 : pp_string (&pp, "??");
267 : }
268 88 : }
269 88 : t.set_cell (table::coord_t (m_x_hex, row_y),
270 176 : styled_string (m_sm, pp_formatted_text (&pp)),
271 : x_align::LEFT);
272 88 : }
273 :
274 : // Try to print ASCII
275 92 : if (m_x_ascii >= 0)
276 : {
277 64 : pretty_printer pp;
278 376 : for (concrete_bit_offset i = bits_on_line.get_start_offset ();
279 376 : i < bits_on_line.get_next_offset ();
280 312 : i += 8_bits)
281 : {
282 312 : if (i + 7_bits < bits_on_line.get_next_offset ())
283 : {
284 312 : auto &byte
285 936 : = bv.get_cropped_bits (concrete_bit_range (i, 8_bits));
286 312 : pp_character (&pp, get_dump_char_for_byte (byte));
287 : }
288 64 : }
289 64 : t.set_cell (table::coord_t (m_x_ascii, row_y),
290 128 : styled_string (m_sm, pp_formatted_text (&pp)),
291 : x_align::LEFT);
292 64 : }
293 92 : }
294 :
295 : static char
296 1812 : get_dump_char_for_tristate_bit (tristate t)
297 : {
298 1812 : switch (t.get_value ())
299 : {
300 0 : default:
301 0 : gcc_unreachable ();
302 : case tristate::TS_UNKNOWN:
303 : return '?';
304 : case tristate::TS_TRUE:
305 : return '1';
306 : case tristate::TS_FALSE:
307 : return '0';
308 : }
309 : }
310 :
311 : static void
312 376 : print_byte_as_hex (pretty_printer *pp, uint8_t byte)
313 : {
314 376 : const char *const hexchars = "0123456789abcdef";
315 376 : pp_character (pp, hexchars[byte / 16]);
316 376 : pp_character (pp, hexchars[byte % 16]);
317 376 : }
318 :
319 : static char
320 312 : get_dump_char_for_byte (const bit_vector &bv)
321 : {
322 312 : uint8_t byte_val;
323 312 : if (!bv.maybe_as_uint8 (&byte_val))
324 : return '?';
325 296 : gcc_assert (byte_val >= 0 && byte_val <= 255);
326 296 : if (ISPRINT (byte_val))
327 244 : return byte_val;
328 : else
329 : return '.';
330 : }
331 :
332 : text_art::style_manager &m_sm;
333 :
334 : const hexdump_options &m_hexdump_opts;
335 : int m_num_columns;
336 : int m_x_bit_range;
337 : int m_x_binary;
338 : int m_x_hex;
339 : int m_x_ascii;
340 : };
341 :
342 : static std::unique_ptr<text_art::canvas>
343 56 : make_hexdump_canvas (const bit_vector &bv,
344 : const hexdump_options &hexdump_opts)
345 : {
346 56 : concrete_bit_size conc_bit_size;
347 56 : if (!concrete_from_symbolic (bv.get_size (), &conc_bit_size))
348 0 : return nullptr;
349 :
350 56 : text_art::style_manager sm;
351 56 : text_art::ascii_theme theme;
352 56 : hexdumper h (sm, hexdump_opts);
353 56 : auto t = h.make_table (bv, conc_bit_size);
354 56 : return std::make_unique<text_art::canvas> (t.to_canvas (theme, sm));
355 56 : }
356 :
357 : void
358 56 : bit_vector::hexdump_to_pp (pretty_printer *pp,
359 : const hexdump_options &hexdump_opts) const
360 : {
361 56 : auto c = make_hexdump_canvas (*this, hexdump_opts);
362 56 : if (!c)
363 0 : return;
364 56 : c->print_to_pp (pp);
365 56 : }
366 :
367 : void
368 0 : bit_vector::hexdump (const hexdump_options &hexdump_opts) const
369 : {
370 0 : tree_dump_pretty_printer pp (stderr);
371 0 : hexdump_to_pp (&pp, hexdump_opts);
372 0 : }
373 :
374 : void
375 0 : bit_vector::hexdump () const
376 : {
377 0 : hexdump_options hexdump_opts;
378 0 : hexdump_opts.m_show_headings = true;
379 0 : hexdump_opts.m_show_binary = false;
380 0 : hexdump_opts.m_show_hex = true;
381 0 : hexdump_opts.m_show_ascii = true;
382 0 : hexdump (hexdump_opts);
383 0 : }
384 :
385 : bool
386 284 : bit_vector::conjured_p () const
387 : {
388 284 : return false;
389 : }
390 :
391 : tristate
392 798956 : bit_vector::get_tristate_at_offset (const concrete_bit_offset &bit) const
393 : {
394 798956 : auto &bit_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bits ();
395 798956 : auto &sym_bit_offset = bit_mgr.get_concrete (bit);
396 798956 : return get_tristate_at_offset (sym_bit_offset);
397 : }
398 :
399 : const bit_vector &
400 18112 : bit_vector::get_cropped_bits (const symbolic_bit_range &bits_to_use) const
401 : {
402 18112 : return m_bv_mgr.get_cropped_bits (*this, bits_to_use);
403 : }
404 :
405 : const bit_vector &
406 2164001 : bit_vector::get_cropped_bits (const concrete_bit_range &bits_to_use) const
407 : {
408 2164001 : auto &bit_mgr = m_bv_mgr.get_bit_manager ();
409 2164001 : return m_bv_mgr.get_cropped_bits (*this,
410 2164001 : symbolic_from_concrete (bits_to_use,
411 2164001 : bit_mgr));
412 : }
413 :
414 : const bit_vector &
415 0 : bit_vector::get_cropped_bytes (const symbolic_byte_range &bytes_to_use) const
416 : {
417 0 : return m_bv_mgr.get_cropped_bits (*this, bits_from_bytes (bytes_to_use));
418 : }
419 :
420 : const bit_vector &
421 140 : bit_vector::get_cropped_bytes (const concrete_byte_range &bytes_to_use) const
422 : {
423 140 : auto &bit_mgr = m_bv_mgr.get_bit_manager ();
424 140 : return m_bv_mgr.get_cropped_bits
425 140 : (*this,
426 280 : symbolic_from_concrete (bits_from_bytes (bytes_to_use),
427 140 : bit_mgr));
428 : }
429 :
430 : /* Get the first SIZE bits of this bit_vector. */
431 :
432 : const bit_vector &
433 925 : bit_vector::get_prefix (const symbolic_bit_size &size) const
434 : {
435 925 : auto &bit_mgr = m_bv_mgr.get_bit_manager ();
436 925 : return m_bv_mgr.get_cropped_bits
437 925 : (*this,
438 925 : symbolic_bit_range (bit_mgr.get_concrete (0_bits),
439 925 : size));
440 : }
441 :
442 : const bit_vector &
443 917 : bit_vector::get_prefix (const concrete_bit_size &size) const
444 : {
445 917 : return get_prefix (symbolic_from_concrete (size,
446 917 : m_bv_mgr.get_bit_manager ()));
447 : }
448 :
449 : /* Get the last SIZE bits of this bit_vector. */
450 :
451 : const bit_vector &
452 1983 : bit_vector::get_suffix (const symbolic_bit_size &size) const
453 : {
454 1983 : return m_bv_mgr.get_cropped_bits (*this,
455 1983 : symbolic_bit_range (get_size () - size,
456 1983 : size));
457 : }
458 :
459 : const bit_vector &
460 1983 : bit_vector::get_suffix (const concrete_bit_size &size) const
461 : {
462 1983 : return get_suffix (symbolic_from_concrete (size,
463 1983 : m_bv_mgr.get_bit_manager ()));
464 : }
465 :
466 : const bit_vector &
467 0 : bit_vector::get_byte_at_offset (const symbolic_byte_offset &byte_offset) const
468 : {
469 0 : auto &byte_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bytes ();
470 0 : return m_bv_mgr.get_cropped_bytes
471 0 : (*this,
472 0 : symbolic_byte_range (byte_offset,
473 0 : byte_mgr.get_concrete (1_byte)));
474 : }
475 :
476 : const bit_vector &
477 475598 : bit_vector::get_byte_at_offset (const concrete_byte_offset &byte_offset) const
478 : {
479 475598 : auto &byte_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bytes ();
480 475598 : return m_bv_mgr.get_cropped_bytes
481 475598 : (*this,
482 951196 : symbolic_byte_range (byte_mgr.get_concrete (byte_offset),
483 475598 : byte_mgr.get_concrete (1_byte)));
484 : }
485 :
486 : const bit_vector *
487 75878 : bit_vector::maybe_fold_crop (const symbolic_bit_range &) const
488 : {
489 75878 : return nullptr;
490 : }
491 :
492 : /* If this is an 8-bit constant value, return true and write it to *OUT.
493 : Otherwise return false. */
494 :
495 : bool
496 477094 : bit_vector::maybe_as_uint8 (uint8_t *out) const
497 : {
498 477094 : concrete_byte_size byte_size;
499 477094 : if (!maybe_get_concrete_size_in_bytes (&byte_size))
500 : return false;
501 477094 : if (byte_size != 1_byte)
502 : return false;
503 :
504 477094 : if (auto *ts = dyn_cast_tristate_bit_vector ())
505 250033 : switch (ts->get_bit_value ().get_value ())
506 : {
507 0 : default:
508 0 : gcc_unreachable ();
509 : case tristate::TS_UNKNOWN:
510 : return false;
511 :
512 84 : case tristate::TS_TRUE:
513 84 : *out = 0xff;
514 84 : return true;
515 :
516 249917 : case tristate::TS_FALSE:
517 249917 : *out = 0x00;
518 249917 : return true;
519 : }
520 :
521 227061 : if (auto *sval_bv = dyn_cast_bit_vector_from_svalue ())
522 : {
523 2425 : auto &sval = sval_bv->get_svalue ();
524 2425 : if (tree type = sval.get_type ())
525 2425 : if (INTEGRAL_TYPE_P (type)
526 2425 : && TYPE_PRECISION (type) == 8)
527 2425 : if (tree cst = sval.maybe_get_constant ())
528 : {
529 2379 : *out = TREE_INT_CST_LOW (cst);
530 2379 : return true;
531 : }
532 : }
533 :
534 : return false;
535 477094 : }
536 :
537 : const bit_vector *
538 70173 : bit_vector::can_merge_p (const bit_vector &bv_a,
539 : const bit_vector &bv_b,
540 : tree type,
541 : model_merger *merger)
542 : {
543 70173 : if (&bv_a == &bv_b)
544 : return &bv_a;
545 :
546 62276 : auto &bv_mgr = bv_a.m_bv_mgr;
547 :
548 : /* Reject attempts to merge poisoned bit vectors with other bit vectors
549 : (either non-poisoned, or other kinds of poison), so that e.g.
550 : we identify paths in which a variable is conditionally uninitialized. */
551 62276 : if (bv_a.get_kind () == kind::poisoned
552 62276 : || bv_b.get_kind () == kind::poisoned)
553 : return nullptr;
554 :
555 61993 : if (!merger->mergeable_bit_vector_p (bv_a))
556 : return nullptr;
557 61198 : if (!merger->mergeable_bit_vector_p (bv_b))
558 : return nullptr;
559 :
560 : /* If we don't have a type, but both bvs are built from svalues with
561 : the same underlying type, try to use that type. */
562 60179 : if (!type)
563 3899 : if (auto *from_sval_a = bv_a.dyn_cast_bit_vector_from_svalue ())
564 933 : if (auto *from_sval_b = bv_b.dyn_cast_bit_vector_from_svalue ())
565 : {
566 672 : tree type_a = from_sval_a->get_svalue ().get_type ();
567 672 : tree type_b = from_sval_b->get_svalue ().get_type ();
568 672 : if (type_a == type_b)
569 3899 : type = type_a;
570 : }
571 :
572 3899 : if (type)
573 : {
574 56944 : auto &rmm = bv_mgr.get_node_manager ().get_svalue_manager ();
575 56944 : const svalue *sval_a = rmm.get_svalue_from_bit_vector (type, bv_a);
576 56944 : const svalue *sval_b = rmm.get_svalue_from_bit_vector (type, bv_b);
577 56944 : if (const svalue *merged_sval = sval_a->can_merge_p (sval_b, &rmm,
578 : merger))
579 43012 : return &bv_mgr.get_bit_vector_from_svalue (*merged_sval);
580 : else
581 : /* svalues not mergeable; don't merge the bit vectors. */
582 : return nullptr;
583 : }
584 :
585 3235 : return &bv_mgr.get_unknown_bits (bv_a.get_size ());
586 : }
587 :
588 : std::unique_ptr<json::object>
589 184 : bit_vector::make_json_obj (const char *type_name) const
590 : {
591 184 : auto obj = value_node::make_json_obj (type_name);
592 184 : obj->set ("size_in_bits", m_size_in_bits.to_json ());
593 184 : return obj;
594 : }
595 :
596 :
597 : static bool
598 23874 : maybe_set_irange_bitmask_from_concrete_tristate_vector (const concrete_tristate_vector &ts_vec,
599 : irange_bitmask *out)
600 : {
601 23874 : unsigned HOST_WIDE_INT value = 0;
602 23874 : unsigned HOST_WIDE_INT mask = -1;
603 812582 : for (size_t i = 0; i < ts_vec.size (); ++i)
604 : {
605 788708 : tristate ts = ts_vec[i];
606 788708 : if (ts.is_known ())
607 : {
608 : /* Clear the mask for known bits. */
609 337 : mask &= ~(1L << i);
610 :
611 : /* Set the value. */
612 337 : if (ts.is_true ())
613 107 : value |= (1L << i);
614 : }
615 : }
616 47748 : *out = irange_bitmask (wi::uhwi (value, ts_vec.size ()),
617 47748 : wi::uhwi (mask, ts_vec.size ()));
618 23874 : return true;
619 : }
620 :
621 : bool
622 23886 : bit_vector::maybe_get_irange_bitmask (irange_bitmask *out) const
623 : {
624 23886 : concrete_bit_size conc_size;
625 23886 : if (!maybe_get_concrete_size_in_bits (&conc_size))
626 : return false;
627 :
628 23886 : if (conc_size > 64_bits)
629 : return false;
630 :
631 23870 : out->set_unknown (conc_size.as_unsigned_long ());
632 23870 : concrete_tristate_vector ts_vec;
633 23870 : ts_vec.reserve (conc_size.as_unsigned_long ());
634 836428 : for (concrete_bit_offset i = 0_bits; i < conc_size; ++i)
635 : {
636 : /* TODO: this is a lot of vfuncs and sym to conc,
637 : and O(n^2) e.g. on concat_bit_vector
638 : We might want a bulk query interface that
639 : returns a concrete_tristate_vector. */
640 788688 : tristate ts = get_tristate_at_offset (i);
641 788688 : ts_vec.push_back (ts);
642 23870 : }
643 23870 : return maybe_set_irange_bitmask_from_concrete_tristate_vector (ts_vec,
644 : out);
645 23870 : }
646 :
647 : /* Return true if this bit vector is the initial value of a region,
648 : or derived directly from such a value (e.g. by casting or cropping). */
649 :
650 : bool
651 9296 : bit_vector::derived_from_initial_value_p () const
652 : {
653 9372 : switch (get_kind ())
654 : {
655 : default:
656 : return false;
657 :
658 76 : case bit_vector::kind::cropped:
659 76 : {
660 76 : auto &cropped_bv = static_cast <const cropped_bit_vector &> (*this);
661 76 : return cropped_bv
662 76 : .get_uncropped_bit_vector ()
663 76 : .derived_from_initial_value_p ();
664 : }
665 :
666 76 : case bit_vector::kind::svalue:
667 76 : {
668 76 : auto &from_sval = static_cast <const bit_vector_from_svalue &> (*this);
669 76 : return from_sval.get_svalue ().derived_from_initial_value_p ();
670 : }
671 : }
672 : }
673 :
674 : // class concat_bit_vector : public bit_vector
675 :
676 : bool
677 213872 : concat_bit_vector::key::operator< (const key &other) const
678 : {
679 213872 : if (m_bit_vectors.size () != other.m_bit_vectors.size ())
680 3765 : return m_bit_vectors.size () < other.m_bit_vectors.size ();
681 357824 : for (size_t i = 0; i < m_bit_vectors.size (); ++i)
682 292314 : if (m_bit_vectors[i] != other.m_bit_vectors[i])
683 144597 : return m_bit_vectors[i]->get_id () < other.m_bit_vectors[i]->get_id ();
684 : return false;
685 : }
686 :
687 : complexity
688 4109 : concat_bit_vector::key::get_complexity () const
689 : {
690 4109 : unsigned num_child_nodes = 0;
691 4109 : unsigned max_child_depth = 0;
692 14015 : for (auto iter : m_bit_vectors)
693 : {
694 9906 : const complexity &child_c = iter->get_complexity ();
695 9906 : num_child_nodes += child_c.m_num_nodes;
696 9906 : max_child_depth = std::max (max_child_depth, child_c.m_max_depth);
697 : }
698 4109 : return complexity (num_child_nodes + 1, max_child_depth + 1);
699 : }
700 :
701 : const symbolic_bit_size &
702 4109 : concat_bit_vector::key::
703 : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
704 : {
705 4109 : const symbolic_bit_size *sum = &bit_mgr.get_concrete (0_bits);
706 14015 : for (auto iter : m_bit_vectors)
707 9906 : sum = &(*sum + iter->get_size ());
708 4109 : return *sum;
709 : }
710 :
711 : tristate
712 10192 : concat_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &bit) const
713 : {
714 10192 : auto *remaining_offset = &bit;
715 17031 : for (auto child : m_bit_vectors)
716 : {
717 : /* Is the bit of interest within child?
718 : | remaining_offset < child->get_size ()
719 : | => (remaining_offset - child->get_size ()) < 0 */
720 17031 : auto &diff = *remaining_offset - child->get_size ();
721 17031 : if (auto *conc_diff = diff.dyn_cast_concrete_scalar ())
722 : {
723 17031 : if (conc_diff->get_concrete () < 0_bits)
724 10192 : return child->get_tristate_at_offset (*remaining_offset);
725 : else
726 : {
727 : /* Skip this child.
728 : | remaining_offset -= child_get_size
729 : | ==> remaining_offset = remaining_offset - child_get_size
730 : | ==> remaining_offset = diff */
731 6839 : remaining_offset = &diff;
732 6839 : continue;
733 : }
734 : }
735 : else
736 : {
737 : /* We don't know whether we're in child or not. */
738 0 : return tristate::unknown ();
739 : }
740 : }
741 0 : return tristate::unknown ();
742 : }
743 :
744 4109 : concat_bit_vector::concat_bit_vector (bit_vector_manager &bv_mgr,
745 : const key &k)
746 : : bit_vector (bv_mgr,
747 : k.get_complexity (),
748 4109 : k.get_size (bv_mgr.get_node_manager ()
749 4109 : .get_scalars ().get_bits ())),
750 4109 : m_bit_vectors (std::move (k.m_bit_vectors))
751 : {
752 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
753 4109 : gcc_assert (!get_size ().is_zero_p ());
754 :
755 : /* After folding, we shouldn't have empty or single-element
756 : concatentations. */
757 4109 : gcc_assert (m_bit_vectors.size () >= 2);
758 :
759 : if (CHECKING_P)
760 9906 : for (auto iter = m_bit_vectors.begin ();
761 14015 : iter != m_bit_vectors.end ();
762 9906 : ++iter)
763 : {
764 : /* No empty children. */
765 9906 : gcc_assert (!(*iter)->get_size ().is_zero_p ());
766 :
767 : /* No nesting. */
768 9906 : gcc_assert (!(*iter)->dyn_cast_concat_bit_vector ());
769 :
770 : /* Check that we folded away consecutive children. */
771 9906 : auto next = iter;
772 9906 : ++next;
773 9906 : if (next != m_bit_vectors.end ())
774 : {
775 : /* Must not have the same bit_vector appearing
776 : consecutively as a child. */
777 5797 : gcc_assert (*iter != *next);
778 :
779 : /* Must not have consecutive children that are the
780 : uniform_bit_vector with the same underlying bit. */
781 5797 : if (auto *iter_poisoned = (*iter)->dyn_cast_poisoned_bit_vector ())
782 106 : if (auto *next_poisoned = (*next)->dyn_cast_poisoned_bit_vector ())
783 4 : gcc_assert (iter_poisoned->get_poison_kind ()
784 : != next_poisoned->get_poison_kind ());
785 5797 : if (auto *iter_tristate = (*iter)->dyn_cast_tristate_bit_vector ())
786 581 : if (auto *next_tristate = (*next)->dyn_cast_tristate_bit_vector ())
787 105 : gcc_assert (iter_tristate->get_bit_value ()
788 : != next_tristate->get_bit_value ());
789 :
790 : /* Must not have consecutive repetitions of the same bit vector,
791 : or a bit vector next to repetitions of that bit vector. */
792 5797 : auto *iter_rep = (*iter)->dyn_cast_repeated_bit_vector ();
793 5797 : auto *next_rep = (*next)->dyn_cast_repeated_bit_vector ();
794 5797 : if (iter_rep)
795 : {
796 184 : if (next_rep)
797 45 : gcc_assert (&iter_rep->get_inner_bit_vector ()
798 : != &next_rep->get_inner_bit_vector ());
799 : else
800 139 : gcc_assert (&iter_rep->get_inner_bit_vector () != (*next));
801 : }
802 5613 : else if (next_rep)
803 100 : gcc_assert ((*iter) != &next_rep->get_inner_bit_vector ());
804 :
805 : /* Must not have consecutive bit_vector_from_ubc taken from the
806 : same UBC at consecutive positions. */
807 5797 : if (auto *iter_from_ubc = (*iter)->dyn_cast_bit_vector_from_ubc ())
808 203 : if (auto *next_from_ubc = (*next)->dyn_cast_bit_vector_from_ubc ())
809 16 : if (&iter_from_ubc->get_bit_contents ()
810 16 : == &next_from_ubc->get_bit_contents ())
811 4 : gcc_assert
812 : (&iter_from_ubc->get_bit_range ().get_next_offset ()
813 : != &next_from_ubc->get_bit_range ().get_start_offset ());
814 : }
815 : }
816 4109 : }
817 :
818 : void
819 14 : concat_bit_vector::
820 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
821 : {
822 14 : pp_string (pp, "concat_bit_vector");
823 14 : }
824 :
825 : void
826 14 : concat_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
827 : node_dump_state &nds) const
828 : {
829 42 : for (auto iter : m_bit_vectors)
830 56 : w.add_child (iter->make_dump_widget (nds, nullptr));
831 14 : }
832 :
833 : void
834 3932 : concat_bit_vector::accept_node_visitor (node_visitor &v) const
835 : {
836 3932 : if (!v.visit_bit_vector (*this))
837 : return;
838 13291 : for (auto iter : m_bit_vectors)
839 9359 : iter->accept_node_visitor (v);
840 : }
841 :
842 : std::unique_ptr<json::object>
843 8 : concat_bit_vector::to_json () const
844 : {
845 8 : auto obj = bit_vector::make_json_obj ("concat_bit_vector");
846 8 : auto arr = std::make_unique<json::array> ();
847 32 : for (auto iter : m_bit_vectors)
848 24 : arr->append (iter->to_json ());
849 8 : obj->set ("bit_vectors", std::move (arr));
850 16 : return obj;
851 8 : }
852 :
853 : std::unique_ptr<diagnostics::markup::node>
854 0 : concat_bit_vector::make_markup_node (markup_context &) const
855 : {
856 0 : return diagnostics::markup::make_text_node ("concat_bit_vector");
857 : }
858 :
859 : iter_result
860 0 : concat_bit_vector::for_each_svalue (iter_result (*cb) (const svalue &sval,
861 : void *user_data),
862 : void *user_data) const
863 : {
864 0 : for (auto iter : m_bit_vectors)
865 0 : if (iter->for_each_svalue (cb, user_data) == iter_result::stop)
866 0 : return iter_result::stop;
867 : return iter_result::keep_going;
868 : }
869 :
870 : bool
871 76 : concat_bit_vector::implicitly_live_p (liveness_context &liveness_ctxt) const
872 : {
873 143 : for (auto iter : m_bit_vectors)
874 143 : if (!liveness_ctxt.node_live_p (*iter))
875 76 : return false;
876 : return true;
877 : }
878 :
879 : /* crop of concat e.g.:
880 : concat(X1, ... Xn)[a, b] --> concat(X1[...], ..., Xn[...])
881 : */
882 : const bit_vector *
883 3145 : concat_bit_vector::
884 : maybe_fold_crop (const symbolic_bit_range &sym_inner_bits_to_use) const
885 : {
886 3145 : concrete_bit_range conc_inner_bits_to_use;
887 3145 : if (!concrete_from_symbolic (sym_inner_bits_to_use, &conc_inner_bits_to_use))
888 : return nullptr;
889 :
890 3145 : std::vector<const bit_vector *> vec_of_cropped;
891 3145 : concrete_bit_size leading_bits_to_ignore
892 3145 : = conc_inner_bits_to_use.get_start_offset ();
893 3145 : concrete_bit_size remaining_bits_to_add
894 3145 : = conc_inner_bits_to_use.get_size ();
895 11459 : for (auto iter : *this)
896 : {
897 11459 : auto &iter_size = iter->get_size ();
898 11459 : concrete_bit_size conc_iter_size;
899 11459 : if (!concrete_from_symbolic (iter_size, &conc_iter_size))
900 0 : return nullptr;
901 :
902 11459 : concrete_bit_size bits_to_use
903 11459 : = std::min (conc_iter_size - leading_bits_to_ignore,
904 11459 : remaining_bits_to_add);
905 11459 : if (bits_to_use > 0_bits)
906 : {
907 3313 : auto &cropped_iter = iter->get_cropped_bits
908 9939 : (concrete_bit_range (leading_bits_to_ignore,
909 9939 : bits_to_use));
910 3313 : vec_of_cropped.push_back (&cropped_iter);
911 3313 : leading_bits_to_ignore = 0_bits;
912 3313 : remaining_bits_to_add -= bits_to_use;
913 : }
914 : else
915 8146 : leading_bits_to_ignore -= conc_iter_size;
916 :
917 11459 : if (remaining_bits_to_add <= 0_bits)
918 : break;
919 11459 : }
920 :
921 3145 : return &m_bv_mgr.get_concat_bits (std::move (vec_of_cropped));
922 3145 : }
923 :
924 : // class conjured_bit_vector : public bit_vector
925 :
926 : bool
927 345807 : conjured_bit_vector::key::operator< (const key &other) const
928 : {
929 345807 : if (int c = m_stmt->uid - other.m_stmt->uid)
930 275541 : return c < 0;
931 70266 : if (int c = node::cmp (*m_id_reg, *other.m_id_reg))
932 27716 : return c < 0;
933 42550 : return m_idx < other.m_idx;
934 : }
935 :
936 : complexity
937 14560 : conjured_bit_vector::key::get_complexity () const
938 : {
939 14560 : return complexity (m_id_reg);
940 : }
941 :
942 : const symbolic_bit_size &
943 14560 : conjured_bit_vector::key::get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
944 : {
945 14560 : auto size = m_id_reg->maybe_get_bit_size (bit_mgr);
946 14560 : if (!size)
947 8894 : size = &bit_mgr.get_unknown ();
948 14560 : return *size;
949 : }
950 :
951 : tristate
952 535492 : conjured_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
953 : {
954 535492 : return tristate::unknown ();
955 : }
956 :
957 14560 : conjured_bit_vector::conjured_bit_vector (bit_vector_manager &bv_mgr,
958 : const key &k)
959 : : bit_vector (bv_mgr,
960 : k.get_complexity (),
961 14560 : k.get_size (bv_mgr.get_node_manager ()
962 14560 : .get_scalars ().get_bits ())),
963 14560 : m_stmt (k.m_stmt),
964 14560 : m_id_reg (k.m_id_reg),
965 14560 : m_idx (k.m_idx)
966 : {
967 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
968 14560 : gcc_assert (!get_size ().is_zero_p ());
969 14560 : }
970 :
971 : void
972 0 : conjured_bit_vector::
973 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
974 : {
975 0 : pp_printf (pp, "conjured_bit_vector (");
976 0 : pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
977 0 : if (m_idx != 0)
978 0 : pp_printf (pp, ", %i", m_idx);
979 0 : pp_character (pp, ')');
980 0 : }
981 :
982 : void
983 0 : conjured_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
984 : node_dump_state &nds) const
985 : {
986 0 : w.add_child (m_id_reg->make_dump_widget (nds, "id_reg"));
987 0 : }
988 :
989 : void
990 1938812 : conjured_bit_vector::accept_node_visitor (node_visitor &v) const
991 : {
992 1938812 : if (!v.visit_bit_vector (*this))
993 : return;
994 1938812 : m_id_reg->accept_node_visitor (v);
995 : }
996 :
997 : std::unique_ptr<json::object>
998 0 : conjured_bit_vector::to_json () const
999 : {
1000 0 : auto obj = bit_vector::make_json_obj ("conjured_bit_vector");
1001 :
1002 0 : {
1003 0 : pretty_printer pp;
1004 0 : pp_format_decoder (&pp) = default_tree_printer;
1005 0 : pp_gimple_stmt_1 (&pp, m_stmt, 0, (dump_flags_t)0);
1006 0 : obj->set_string ("stmt", pp_formatted_text (&pp));
1007 0 : }
1008 0 : obj->set ("id_reg", m_id_reg->to_json ());
1009 0 : obj->set_integer ("id", m_idx);
1010 :
1011 0 : return obj;
1012 : }
1013 :
1014 : std::unique_ptr<diagnostics::markup::node>
1015 12 : conjured_bit_vector::make_markup_node (markup_context &markup_ctxt) const
1016 : {
1017 12 : if (markup_ctxt.m_user_facing)
1018 12 : return m_id_reg->make_markup_node (markup_ctxt);
1019 :
1020 0 : auto markup = std::make_unique<diagnostics::markup::compound_node> ();
1021 0 : markup->add_child ("conjured_bit_vector(");
1022 0 : markup->add_child (")");
1023 0 : return markup;
1024 0 : }
1025 :
1026 : iter_result
1027 1050 : conjured_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1028 : void *user_data),
1029 : void *) const
1030 : {
1031 1050 : return iter_result::keep_going;
1032 : }
1033 :
1034 : // class cropped_bit_vector : public bit_vector
1035 :
1036 : bool
1037 419753 : cropped_bit_vector::key::operator< (const key &other) const
1038 : {
1039 419753 : if (int c = node::cmp (*m_uncropped_bv,
1040 419753 : *other.m_uncropped_bv))
1041 190612 : return c < 0;
1042 392959 : return symbolic_bit_range::cmp (m_bits_to_use, other.m_bits_to_use) < 0;
1043 : }
1044 :
1045 : tristate
1046 9672 : cropped_bit_vector::
1047 : get_tristate_at_offset (const symbolic_bit_offset &bit) const
1048 : {
1049 9672 : return m_uncropped_bv.get_tristate_at_offset
1050 9672 : (m_crop_start_bit_offset + bit);
1051 : }
1052 :
1053 7367 : cropped_bit_vector::cropped_bit_vector (bit_vector_manager &bv_mgr,
1054 : const key &k)
1055 : : bit_vector (bv_mgr,
1056 7367 : complexity (*k.m_uncropped_bv),
1057 : k.get_size ()),
1058 7367 : m_uncropped_bv (*k.m_uncropped_bv),
1059 7367 : m_crop_start_bit_offset (k.m_bits_to_use.get_start_offset ())
1060 : {
1061 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1062 7367 : gcc_assert (!get_size ().is_zero_p ());
1063 :
1064 : /* No nesting. */
1065 7367 : gcc_assert (!m_uncropped_bv.dyn_cast_cropped_bit_vector ());
1066 :
1067 : /* Cropping of a uniform_bit_vector should have been folded
1068 : before now. */
1069 7367 : gcc_assert (!m_uncropped_bv.dyn_cast_uniform_bit_vector ());
1070 7367 : }
1071 :
1072 : void
1073 7 : cropped_bit_vector::
1074 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1075 : {
1076 7 : pp_string (pp, "cropped_bit_vector");
1077 7 : }
1078 :
1079 : void
1080 7 : cropped_bit_vector::
1081 : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
1082 : {
1083 7 : concrete_bit_range conc_bits;
1084 7 : if (concrete_from_symbolic (get_uncropped_bits_to_use (), &conc_bits))
1085 : {
1086 7 : pp_string (pp, ": ");
1087 7 : end_any_dump_color (pp);
1088 7 : m_size_in_bits.start_any_dump_color (pp);
1089 7 : conc_bits.dump_to_pp_pretty (pp);
1090 : }
1091 7 : }
1092 :
1093 : void
1094 7 : cropped_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
1095 : node_dump_state &nds) const
1096 : {
1097 14 : w.add_child (m_uncropped_bv.make_dump_widget (nds, "uncropped"));
1098 7 : concrete_bit_range conc_bits;
1099 7 : if (!concrete_from_symbolic (get_uncropped_bits_to_use (), &conc_bits))
1100 0 : w.add_child (get_uncropped_bits_to_use ().make_dump_widget (nds,
1101 : "bits to use"));
1102 7 : }
1103 :
1104 : void
1105 52670 : cropped_bit_vector::accept_node_visitor (node_visitor &v) const
1106 : {
1107 52670 : if (!v.visit_bit_vector (*this))
1108 : return;
1109 271 : m_uncropped_bv.accept_node_visitor (v);
1110 : }
1111 :
1112 : std::unique_ptr<json::object>
1113 4 : cropped_bit_vector::to_json () const
1114 : {
1115 4 : auto obj = bit_vector::make_json_obj ("cropped_bit_vector");
1116 4 : obj->set ("crop_start_bit_offset", m_crop_start_bit_offset.to_json ());
1117 4 : obj->set ("uncropped_bv", m_uncropped_bv.to_json ());
1118 4 : return obj;
1119 : }
1120 :
1121 : std::unique_ptr<diagnostics::markup::node>
1122 0 : cropped_bit_vector::make_markup_node (markup_context &markup_ctxt) const
1123 : {
1124 0 : auto result = std::make_unique<diagnostics::markup::compound_node> ();
1125 0 : result->add_child ("cropped_bit_vector (start_bit_offset=");
1126 0 : result->add_child (m_crop_start_bit_offset.make_markup_node (markup_ctxt));
1127 0 : result->add_child (", uncropped_bv=");
1128 0 : result->add_child (m_uncropped_bv.make_markup_node (markup_ctxt));
1129 0 : result->add_child (")");
1130 0 : return result;
1131 0 : }
1132 :
1133 : iter_result
1134 43 : cropped_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1135 : void *user_data),
1136 : void *) const
1137 : {
1138 43 : return iter_result::keep_going;
1139 : }
1140 :
1141 : bool
1142 732 : cropped_bit_vector::implicitly_live_p (liveness_context &liveness_ctxt) const
1143 : {
1144 732 : return m_uncropped_bv.implicitly_live_p (liveness_ctxt);
1145 : }
1146 :
1147 : /* Crop of crop: A[m..n][p..q] --> A[m + n .. m + n + sizeof(p..q)]. */
1148 :
1149 : const bit_vector *
1150 2173 : cropped_bit_vector::
1151 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1152 : {
1153 2173 : symbolic_bit_range bit_range_relative_to_grandchild
1154 2173 : ((get_uncropped_bits_to_use ().get_start_offset ()
1155 : + bits_to_use.get_start_offset ()),
1156 2173 : bits_to_use.get_size ());
1157 2173 : return &m_bv_mgr.get_cropped_bits (get_uncropped_bit_vector (),
1158 2173 : bit_range_relative_to_grandchild);
1159 : }
1160 :
1161 : // class named_test_bit_vector : public bit_vector
1162 :
1163 : #if CHECKING_P
1164 :
1165 : tristate
1166 0 : named_test_bit_vector::
1167 : get_tristate_at_offset (const symbolic_bit_offset &) const
1168 : {
1169 0 : return tristate::unknown ();
1170 : }
1171 :
1172 128 : named_test_bit_vector::
1173 : named_test_bit_vector (bit_vector_manager &bv_mgr,
1174 : const symbolic_bit_size &size_in_bits,
1175 : std::string label)
1176 128 : : bit_vector (bv_mgr, complexity (1, 1), size_in_bits),
1177 128 : m_label (std::move (label))
1178 : {
1179 128 : }
1180 :
1181 : void
1182 8 : named_test_bit_vector::
1183 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1184 : {
1185 8 : pp_string (pp, "named_test_bit_vector");
1186 8 : }
1187 :
1188 : void
1189 8 : named_test_bit_vector::
1190 : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
1191 : {
1192 8 : pp_printf (pp, ": %qs", m_label.c_str ());
1193 8 : }
1194 :
1195 : void
1196 8 : named_test_bit_vector::add_dump_widget_children (text_art::tree_widget &,
1197 : node_dump_state &) const
1198 : {
1199 : // no-op
1200 8 : }
1201 :
1202 : void
1203 0 : named_test_bit_vector::accept_node_visitor (node_visitor &v) const
1204 : {
1205 0 : v.visit_bit_vector (*this);
1206 0 : }
1207 :
1208 : std::unique_ptr<json::object>
1209 28 : named_test_bit_vector::to_json () const
1210 : {
1211 28 : auto obj = bit_vector::make_json_obj ("named_test_bit_vector");
1212 56 : obj->set_string ("label", m_label);
1213 28 : return obj;
1214 : }
1215 :
1216 : std::unique_ptr<diagnostics::markup::node>
1217 0 : named_test_bit_vector::make_markup_node (markup_context &) const
1218 : {
1219 0 : return diagnostics::markup::make_text_node (m_label);
1220 : }
1221 :
1222 : iter_result
1223 0 : named_test_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1224 : void *user_data),
1225 : void *) const
1226 : {
1227 0 : return iter_result::keep_going;
1228 : }
1229 :
1230 : #endif /* #if CHECKING_P */
1231 :
1232 : // class empty_bit_vector : public bit_vector
1233 :
1234 : tristate
1235 0 : empty_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
1236 : {
1237 : /* This should never be called; there are no bits to query. */
1238 0 : gcc_unreachable ();
1239 : }
1240 :
1241 4409 : empty_bit_vector::empty_bit_vector (bit_vector_manager &bv_mgr)
1242 : : uniform_bit_vector (bv_mgr,
1243 4409 : complexity (1, 1),
1244 4409 : (bv_mgr.get_node_manager ()
1245 4409 : .get_scalars ().get_bits ().get_concrete (0_bits)))
1246 : {
1247 4409 : }
1248 :
1249 : void
1250 0 : empty_bit_vector::
1251 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1252 : {
1253 0 : pp_string (pp, "empty_bit_vector");
1254 0 : }
1255 :
1256 : void
1257 0 : empty_bit_vector::add_dump_widget_children (text_art::tree_widget &,
1258 : node_dump_state &) const
1259 : {
1260 : // No-op
1261 0 : }
1262 :
1263 : void
1264 42 : empty_bit_vector::accept_node_visitor (node_visitor &v) const
1265 : {
1266 42 : v.visit_bit_vector (*this);
1267 42 : }
1268 :
1269 : std::unique_ptr<json::object>
1270 4 : empty_bit_vector::to_json () const
1271 : {
1272 4 : return bit_vector::make_json_obj ("empty_bit_vector");
1273 : }
1274 :
1275 : std::unique_ptr<diagnostics::markup::node>
1276 0 : empty_bit_vector::make_markup_node (markup_context &) const
1277 : {
1278 0 : return diagnostics::markup::make_text_node ("empty_bit_vector");
1279 : }
1280 :
1281 : iter_result
1282 0 : empty_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1283 : void *user_data),
1284 : void *) const
1285 : {
1286 0 : return iter_result::keep_going;
1287 : }
1288 :
1289 : // class poisoned_bit_vector : public bit_vector
1290 :
1291 : bool
1292 6410033 : poisoned_bit_vector::key::operator< (const key &other) const
1293 : {
1294 6410033 : if (int c = node::cmp (m_size_in_bits, other.m_size_in_bits))
1295 3104415 : return c < 0;
1296 3305618 : return (int)m_poison_kind < (int)other.m_poison_kind;
1297 : }
1298 :
1299 : tristate
1300 22647 : poisoned_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
1301 : {
1302 22647 : return tristate::unknown ();
1303 : }
1304 :
1305 12436 : poisoned_bit_vector::poisoned_bit_vector (bit_vector_manager &bv_mgr,
1306 : const key &k)
1307 : : uniform_bit_vector (bv_mgr,
1308 12436 : complexity (1, 1),
1309 : k.m_size_in_bits),
1310 12436 : m_poison_kind (k.m_poison_kind)
1311 : {
1312 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1313 12436 : gcc_assert (!get_size ().is_zero_p ());
1314 12436 : }
1315 :
1316 : void
1317 20 : poisoned_bit_vector::
1318 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1319 : {
1320 20 : pp_string (pp, "poisoned_bit_vector");
1321 20 : }
1322 :
1323 : void
1324 20 : poisoned_bit_vector::
1325 : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
1326 : {
1327 20 : pp_printf (pp, ": %s", poison_kind_to_str (m_poison_kind));
1328 20 : }
1329 :
1330 : void
1331 20 : poisoned_bit_vector::add_dump_widget_children (text_art::tree_widget &,
1332 : node_dump_state &) const
1333 : {
1334 : // no-op
1335 20 : }
1336 :
1337 : void
1338 20520 : poisoned_bit_vector::accept_node_visitor (node_visitor &v) const
1339 : {
1340 20520 : v.visit_bit_vector (*this);
1341 20520 : }
1342 :
1343 : std::unique_ptr<json::object>
1344 8 : poisoned_bit_vector::to_json () const
1345 : {
1346 8 : auto obj = bit_vector::make_json_obj ("poisoned_bit_vector");
1347 8 : obj->set_string ("poison_kind", poison_kind_to_str (m_poison_kind));
1348 8 : return obj;
1349 : }
1350 :
1351 : std::unique_ptr<diagnostics::markup::node>
1352 0 : poisoned_bit_vector::make_markup_node (markup_context &) const
1353 : {
1354 0 : return diagnostics::markup::make_text_node ("poisoned_bit_vector");
1355 : }
1356 :
1357 : iter_result
1358 18 : poisoned_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1359 : void *user_data),
1360 : void *) const
1361 : {
1362 18 : return iter_result::keep_going;
1363 : }
1364 :
1365 : /* poisoned(x)[m..n] --> poisoned(x, sizeof(m..n)). */
1366 :
1367 : const bit_vector *
1368 52766 : poisoned_bit_vector::
1369 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1370 : {
1371 52766 : return &m_bv_mgr.get_poisoned_bits (bits_to_use.get_size (),
1372 52766 : get_poison_kind ());
1373 : }
1374 :
1375 : // class repeated_bit_vector : public bit_vector
1376 :
1377 : bool
1378 2000 : repeated_bit_vector::key::operator< (const key &other) const
1379 : {
1380 2000 : if (m_inner_bv != other.m_inner_bv)
1381 834 : return m_inner_bv->get_id () < other.m_inner_bv->get_id ();
1382 1166 : return m_repeat_count < other.m_repeat_count;
1383 : }
1384 :
1385 294 : repeated_bit_vector::repeated_bit_vector (bit_vector_manager &bv_mgr,
1386 : const key &k)
1387 : : bit_vector (bv_mgr,
1388 294 : complexity (*k.m_inner_bv),
1389 : k.get_size ()),
1390 294 : m_inner_bv (*k.m_inner_bv),
1391 588 : m_repeat_count (*k.m_repeat_count)
1392 : {
1393 294 : gcc_assert (!m_repeat_count.is_zero_p ());
1394 294 : gcc_assert (!m_repeat_count.is_one_p ());
1395 :
1396 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1397 294 : gcc_assert (!get_size ().is_zero_p ());
1398 :
1399 : /* No nesting. */
1400 294 : gcc_assert (!m_inner_bv.dyn_cast_repeated_bit_vector ());
1401 :
1402 : /* Repetition of a uniform_bit_vector should have been folded
1403 : before now. */
1404 294 : gcc_assert (!m_inner_bv.dyn_cast_uniform_bit_vector ());
1405 294 : }
1406 :
1407 : void
1408 0 : repeated_bit_vector::
1409 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1410 : {
1411 0 : pp_string (pp, "repeated_bit_vector");
1412 0 : }
1413 :
1414 : void
1415 0 : repeated_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
1416 : node_dump_state &nds) const
1417 : {
1418 0 : w.add_child (m_inner_bv.make_dump_widget (nds, "m_inner_bv"));
1419 0 : w.add_child (m_repeat_count.make_dump_widget (nds, "m_repeat_count"));
1420 0 : }
1421 :
1422 : void
1423 115631 : repeated_bit_vector::accept_node_visitor (node_visitor &v) const
1424 : {
1425 115631 : if (!v.visit_bit_vector (*this))
1426 : return;
1427 115631 : m_inner_bv.accept_node_visitor (v);
1428 : }
1429 :
1430 : std::unique_ptr<json::object>
1431 4 : repeated_bit_vector::to_json () const
1432 : {
1433 4 : auto obj = bit_vector::make_json_obj ("repeated_bit_vector");
1434 4 : obj->set ("inner_bv", m_inner_bv.to_json ());
1435 4 : obj->set ("repeat_count", m_repeat_count.to_json ());
1436 4 : return obj;
1437 : }
1438 :
1439 : std::unique_ptr<diagnostics::markup::node>
1440 0 : repeated_bit_vector::make_markup_node (markup_context &) const
1441 : {
1442 0 : return diagnostics::markup::make_text_node ("repeated_bit_vector");
1443 : }
1444 :
1445 : iter_result
1446 483 : repeated_bit_vector::for_each_svalue (iter_result (*cb) (const svalue &sval,
1447 : void *user_data),
1448 : void *user_data) const
1449 : {
1450 483 : return m_inner_bv.for_each_svalue (cb, user_data);
1451 : }
1452 :
1453 : const bit_vector *
1454 2456 : repeated_bit_vector::
1455 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1456 : {
1457 2456 : concrete_bit_range conc_bits_to_use;
1458 2456 : if (!concrete_from_symbolic (bits_to_use, &conc_bits_to_use))
1459 : return nullptr;
1460 :
1461 2456 : concrete_bit_size conc_bit_size;
1462 2456 : if (!concrete_from_symbolic (get_size (), &conc_bit_size))
1463 : return nullptr;
1464 :
1465 2456 : concrete_bit_size conc_inner_bit_size;
1466 2456 : if (!concrete_from_symbolic (m_inner_bv.get_size (),
1467 : &conc_inner_bit_size))
1468 : return nullptr;
1469 :
1470 2456 : concrete_bit_size remaining_bits_to_add = conc_bits_to_use.get_size ();
1471 :
1472 2456 : std::vector<const bit_vector *> vec_of_cropped;
1473 :
1474 : /* Do we have a leading fragment from one of the iterations? */
1475 2456 : concrete_bit_offset bit_offset_within_repeat
1476 2456 : = conc_bits_to_use.get_start_offset ().floor_mod (conc_inner_bit_size);
1477 2456 : if (bit_offset_within_repeat > 0_bits)
1478 : {
1479 796 : concrete_bit_size leading_size
1480 796 : = std::min (conc_inner_bit_size - bit_offset_within_repeat,
1481 796 : remaining_bits_to_add);
1482 796 : auto &leading_suffix = m_inner_bv.get_cropped_bits
1483 1592 : (concrete_bit_range (bit_offset_within_repeat,
1484 2388 : leading_size));
1485 796 : vec_of_cropped.push_back (&leading_suffix);
1486 796 : remaining_bits_to_add -= leading_size;
1487 796 : }
1488 :
1489 : /* Do we have any full iterations of the inner bv? */
1490 2456 : integer num_full_repeats
1491 2456 : = remaining_bits_to_add.floor_div (conc_inner_bit_size);
1492 2456 : if (num_full_repeats > 0)
1493 : {
1494 1525 : auto &full_repeats = m_bv_mgr.get_repeated_bits (m_inner_bv,
1495 : num_full_repeats);
1496 1525 : vec_of_cropped.push_back (&full_repeats);
1497 1525 : remaining_bits_to_add -= (conc_inner_bit_size * num_full_repeats);
1498 : }
1499 :
1500 : /* Do we have a trailing suffix from one of the iterations? */
1501 2456 : if (remaining_bits_to_add > 0_bits)
1502 : {
1503 147 : gcc_assert (remaining_bits_to_add < conc_inner_bit_size);
1504 147 : auto &trailing_prefix
1505 147 : = m_inner_bv.get_prefix (remaining_bits_to_add);
1506 147 : vec_of_cropped.push_back (&trailing_prefix);
1507 : }
1508 :
1509 2456 : return &m_bv_mgr.get_concat_bits (std::move (vec_of_cropped));
1510 7368 : }
1511 :
1512 : // class bit_vector_from_svalue : public bit_vector
1513 :
1514 : bool
1515 31578370 : bit_vector_from_svalue::key::operator< (const key &other) const
1516 : {
1517 31578370 : if (m_sval != other.m_sval)
1518 31004198 : return m_sval->get_id () < other.m_sval->get_id ();
1519 : return false;
1520 : }
1521 :
1522 : const symbolic_bit_size &
1523 1179793 : bit_vector_from_svalue::key::
1524 : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
1525 : {
1526 1179793 : concrete_bit_size conc_size;
1527 1179793 : bool has_size = m_sval->has_concrete_size_p (&conc_size,
1528 : bit_mgr);
1529 1179793 : gcc_assert (has_size);
1530 1179793 : return bit_mgr.get_concrete (conc_size);
1531 1179793 : }
1532 :
1533 : tristate
1534 17280 : bit_vector_from_svalue::
1535 : get_tristate_at_offset (const symbolic_bit_offset &bit) const
1536 : {
1537 17280 : auto &bit_mgr = bit.get_mgr ();
1538 17280 : auto &cropped_bit
1539 17280 : = get_cropped_bits (symbolic_bit_range (bit, bit_mgr.get_concrete (1_bit)));
1540 17280 : if (auto *tristate_bit = cropped_bit.dyn_cast_tristate_bit_vector ())
1541 8896 : return tristate_bit->get_bit_value ();
1542 :
1543 8384 : return tristate::unknown ();
1544 : }
1545 :
1546 1179793 : bit_vector_from_svalue::bit_vector_from_svalue (bit_vector_manager &bv_mgr,
1547 : const key &k)
1548 : : bit_vector (bv_mgr,
1549 1179793 : complexity (*k.m_sval),
1550 1179793 : k.get_size (bv_mgr.get_node_manager ()
1551 1179793 : .get_scalars ().get_bits ())),
1552 2359586 : m_sval (*k.m_sval)
1553 : {
1554 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1555 1179793 : gcc_assert (!get_size ().is_zero_p ());
1556 :
1557 : // No nesting
1558 1179793 : gcc_assert (!m_sval.dyn_cast_svalue_from_bit_vector ());
1559 1179793 : }
1560 :
1561 : void
1562 1755 : bit_vector_from_svalue::
1563 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1564 : {
1565 1755 : pp_string (pp, "bit_vector_from_svalue");
1566 1755 : }
1567 :
1568 : void
1569 1755 : bit_vector_from_svalue::
1570 : add_dump_widget_children (text_art::tree_widget &w,
1571 : node_dump_state &nds) const
1572 : {
1573 3510 : w.add_child (m_sval.make_dump_widget (nds, "m_sval"));
1574 1755 : }
1575 :
1576 : bool
1577 0 : bit_vector_from_svalue::
1578 : maybe_print_for_user (pretty_printer *pp,
1579 : const region_model &model,
1580 : const symbolic::node *outer_node) const
1581 : {
1582 0 : return m_sval.maybe_print_for_user (pp, model, nullptr);
1583 : }
1584 :
1585 : void
1586 5190289 : bit_vector_from_svalue::accept_node_visitor (node_visitor &v) const
1587 : {
1588 5190289 : if (!v.visit_bit_vector (*this))
1589 : return;
1590 5190289 : m_sval.accept_node_visitor (v);
1591 : }
1592 :
1593 : std::unique_ptr<json::object>
1594 88 : bit_vector_from_svalue::to_json () const
1595 : {
1596 88 : auto obj = bit_vector::make_json_obj ("bit_vector_from_svalue");
1597 88 : obj->set ("sval", m_sval.to_json ());
1598 88 : return obj;
1599 : }
1600 :
1601 : std::unique_ptr<diagnostics::markup::node>
1602 0 : bit_vector_from_svalue::make_markup_node (markup_context &markup_ctxt) const
1603 : {
1604 0 : return m_sval.make_markup_node (markup_ctxt);
1605 : }
1606 :
1607 : iter_result
1608 6895 : bit_vector_from_svalue::for_each_svalue (iter_result (*cb) (const svalue &sval,
1609 : void *user_data),
1610 : void *user_data) const
1611 : {
1612 6895 : return m_sval.for_each_svalue (cb, user_data);
1613 : }
1614 :
1615 : const bit_vector *
1616 25808 : bit_vector_from_svalue::
1617 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1618 : {
1619 25808 : concrete_bit_range conc_bits_to_use;
1620 25808 : if (!concrete_from_symbolic (bits_to_use, &conc_bits_to_use))
1621 : return nullptr;
1622 :
1623 25808 : if (auto *folded = maybe_fold_crop_from_cst (conc_bits_to_use))
1624 : return folded;
1625 :
1626 12148 : if (auto *folded = maybe_fold_crop_from_bitmask (conc_bits_to_use))
1627 : return folded;
1628 :
1629 : return nullptr;
1630 25808 : }
1631 :
1632 : const bit_vector *
1633 25808 : bit_vector_from_svalue::
1634 : maybe_fold_crop_from_cst (const concrete_bit_range &inner_bits_to_use) const
1635 : {
1636 : /* Attempt to extract bytes from constants. */
1637 25808 : tree tree_cst = m_sval.maybe_get_constant ();
1638 25808 : if (!tree_cst)
1639 12990 : if (auto *init_sval = m_sval.dyn_cast_initial_svalue ())
1640 12152 : if (auto *string_reg
1641 12152 : = init_sval->get_region ()->dyn_cast_string_region ())
1642 1160 : tree_cst = string_reg->get_string_cst ();
1643 12990 : if (!tree_cst)
1644 : return nullptr;
1645 :
1646 13978 : concrete_byte_range conc_bytes_to_use;
1647 13978 : concrete_bit_offset bit_offset;
1648 13978 : get_smallest_enclosing_byte_range (inner_bits_to_use,
1649 : &conc_bytes_to_use,
1650 : &bit_offset);
1651 13978 : gcc_assert (bit_offset < 8_bits);
1652 27956 : if (auto p = m_bv_mgr.maybe_fold_bytes_within_constant (tree_cst,
1653 : conc_bytes_to_use))
1654 : {
1655 13660 : auto effective_size = inner_bits_to_use.get_size ();
1656 13660 : if (p == this)
1657 : {
1658 : /* We're looking at bits within one of the m_cached_bytes
1659 : instances; we need to avoid infinite recursion. */
1660 9291 : gcc_assert (TREE_TYPE (tree_cst) == unsigned_char_type_node);
1661 9291 : gcc_assert (effective_size < 8_bits);
1662 9291 : int byte_val = TREE_INT_CST_LOW (tree_cst);
1663 9291 : gcc_assert (this == &m_bv_mgr.get_uint8 (byte_val));
1664 9291 : std::vector<const symbolic::bit_vector *> raw_bits;
1665 9291 : int idx_after_bits
1666 9291 : = bit_offset.as_long () + effective_size.as_long ();
1667 9291 : for (int bit_idx = bit_offset.as_long ();
1668 18582 : bit_idx < idx_after_bits; ++bit_idx)
1669 : {
1670 : /* Add in LSB through MSB order. */
1671 9291 : bool bit_val = byte_val & (1 << bit_idx);
1672 9291 : raw_bits.push_back
1673 14091 : (&m_bv_mgr.get_tristate_bits (1_bit, tristate (bit_val)));
1674 : }
1675 9291 : return &m_bv_mgr.get_concat_bits (std::move (raw_bits));
1676 9291 : }
1677 : else
1678 4369 : return &p->get_cropped_bits
1679 13107 : (concrete_bit_range (bit_offset, effective_size));
1680 13660 : }
1681 :
1682 : return nullptr;
1683 27956 : }
1684 :
1685 : const bit_vector *
1686 12148 : bit_vector_from_svalue::
1687 : maybe_fold_crop_from_bitmask (const concrete_bit_range &inner_bits_to_use) const
1688 : {
1689 12148 : if (inner_bits_to_use.get_next_offset () > 64_bits)
1690 : return nullptr;
1691 :
1692 8209 : value_range vr;
1693 8209 : if (!m_sval.maybe_get_value_range (vr))
1694 : return nullptr;
1695 :
1696 885 : irange_bitmask bitmask = vr.get_bitmask ();
1697 :
1698 : /* The unknown bits are those for which the mask is one.
1699 : Bail out if we have any unknown bits in the bit_range of interest. */
1700 885 : unsigned HOST_WIDE_INT mask_for_bits
1701 : = wi::extract_uhwi
1702 885 : (bitmask.mask (),
1703 1955 : inner_bits_to_use.get_start_offset ().as_unsigned_long (),
1704 885 : inner_bits_to_use.get_size ().as_unsigned_long ());
1705 885 : if (mask_for_bits != 0)
1706 : return nullptr;
1707 :
1708 : // We have known bits; get their value.
1709 456 : unsigned HOST_WIDE_INT known_value
1710 : = wi::extract_uhwi
1711 456 : (bitmask.value (),
1712 928 : inner_bits_to_use.get_start_offset ().as_unsigned_long (),
1713 456 : inner_bits_to_use.get_size ().as_unsigned_long ());
1714 456 : if (inner_bits_to_use.get_size ().is_one_p ())
1715 720 : return &m_bv_mgr.get_tristate_bits (1_bit, known_value != 0);
1716 32 : else if (inner_bits_to_use.get_size () == 8_bits)
1717 32 : return &m_bv_mgr.get_uint8 (known_value);
1718 : else
1719 : return nullptr;
1720 8209 : }
1721 :
1722 : bool
1723 704 : bit_vector_from_svalue::
1724 : implicitly_live_p (symbolic::liveness_context &liveness_ctxt) const
1725 : {
1726 704 : return liveness_ctxt.node_live_p (m_sval);
1727 : }
1728 :
1729 : // class bit_vector_from_ubc : public bit_vector
1730 :
1731 : tristate
1732 222076 : bit_vector_from_ubc::
1733 : get_tristate_at_offset (const symbolic_bit_offset &) const
1734 : {
1735 222076 : return tristate::unknown ();
1736 : }
1737 :
1738 14543 : bit_vector_from_ubc::
1739 : bit_vector_from_ubc (const unfoldable_bit_contents &bc,
1740 : symbolic_bit_range bit_range)
1741 14543 : : bit_vector (bc.get_node_mgr ().get_bit_vector_manager (),
1742 : complexity::from_pair
1743 : (bc.get_complexity (),
1744 29086 : bit_range.get_children_complexity ()),
1745 : // FIXME: what about symbolic?
1746 14543 : bit_range.get_size ()),
1747 14543 : m_unfoldable_bit_contents (bc),
1748 14543 : m_bit_range (bit_range)
1749 : {
1750 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1751 14543 : gcc_assert (!get_size ().is_zero_p ());
1752 14543 : }
1753 :
1754 : void
1755 587 : bit_vector_from_ubc::
1756 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1757 : {
1758 587 : pp_string (pp, "bit_vector_from_ubc");
1759 587 : }
1760 :
1761 : void
1762 576 : bit_vector_from_ubc::
1763 : add_dump_widget_children (text_art::tree_widget &w,
1764 : node_dump_state &nds) const
1765 : {
1766 576 : w.add_child
1767 1152 : (m_unfoldable_bit_contents.make_dump_widget (nds, "bit_contents"));
1768 1152 : w.add_child (m_bit_range.make_dump_widget (nds, "range"));
1769 576 : }
1770 :
1771 : void
1772 14424718 : bit_vector_from_ubc::accept_node_visitor (node_visitor &v) const
1773 : {
1774 14424718 : if (!v.visit_bit_vector (*this))
1775 : return;
1776 14424718 : m_unfoldable_bit_contents.accept_node_visitor (v);
1777 14424718 : m_bit_range.accept_node_visitor (v);
1778 : }
1779 :
1780 : bool
1781 126343 : bit_vector_from_ubc::conjured_p () const
1782 : {
1783 126343 : return m_unfoldable_bit_contents.conjured_p ();
1784 : }
1785 :
1786 : std::unique_ptr<json::object>
1787 0 : bit_vector_from_ubc::to_json () const
1788 : {
1789 0 : auto obj
1790 0 : = bit_vector::make_json_obj ("bit_vector_from_ubc");
1791 0 : obj->set ("bit_contents", m_unfoldable_bit_contents.to_json ());
1792 0 : obj->set ("bit_range", m_bit_range.to_json ());
1793 0 : return obj;
1794 : }
1795 :
1796 : std::unique_ptr<diagnostics::markup::node>
1797 0 : bit_vector_from_ubc::make_markup_node (markup_context &) const
1798 : {
1799 0 : return diagnostics::markup::make_text_node ("bit_vector_from_ubc");
1800 : }
1801 :
1802 : iter_result
1803 14559 : bit_vector_from_ubc::for_each_svalue (iter_result (*) (const svalue &sval,
1804 : void *user_data),
1805 : void *) const
1806 : {
1807 14559 : return iter_result::keep_going;
1808 : }
1809 :
1810 : bool
1811 287978 : bit_vector_from_ubc::
1812 : implicitly_live_p (symbolic::liveness_context &liveness_ctxt) const
1813 : {
1814 287978 : return liveness_ctxt.bits_live_p (*this);
1815 : }
1816 :
1817 : /* crop(bit_vector_from_ubc (UBC, RANGE), SUBRANGE)
1818 : --> bit_vector_from_ubc (UBC, SUBRANGE OF RANGE). */
1819 :
1820 : const bit_vector *
1821 81571 : bit_vector_from_ubc::
1822 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1823 : {
1824 81571 : auto &result_size = bits_to_use.get_size ();
1825 81571 : symbolic_bit_range subrange
1826 81571 : (get_bit_range ().get_start_offset ()
1827 : + bits_to_use.get_start_offset (),
1828 81571 : result_size);
1829 81571 : return &get_bit_contents ().get_bits (subrange);
1830 : }
1831 :
1832 : // class tristate_bit_vector : public bit_vector
1833 :
1834 : bool
1835 2505688 : tristate_bit_vector::key::operator< (const key &other) const
1836 : {
1837 2505688 : if (int c = node::cmp (m_size_in_bits, other.m_size_in_bits))
1838 686638 : return c < 0;
1839 1819050 : return (static_cast<int> (m_bit_value.get_value ())
1840 1819050 : < static_cast<int> (other.m_bit_value.get_value ()));
1841 : }
1842 :
1843 : tristate
1844 633 : tristate_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
1845 : {
1846 633 : return m_bit_value;
1847 : }
1848 :
1849 19441 : tristate_bit_vector::tristate_bit_vector (bit_vector_manager &bv_mgr,
1850 : const key &k)
1851 19441 : : uniform_bit_vector (bv_mgr, complexity (1, 1), k.m_size_in_bits),
1852 19441 : m_bit_value (k.m_bit_value)
1853 : {
1854 : /* The only empty bit_vector should be the singleton empty_bit_vector. */
1855 19441 : gcc_assert (!get_size ().is_zero_p ());
1856 19441 : }
1857 :
1858 : void
1859 363 : tristate_bit_vector::
1860 : print_prefix_for_dump_widget_label (pretty_printer *pp) const
1861 : {
1862 363 : pp_string (pp, "tristate_bit_vector");
1863 363 : }
1864 :
1865 : void
1866 363 : tristate_bit_vector::
1867 : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
1868 : {
1869 363 : pp_string (pp, ": ");
1870 363 : if (m_size_in_bits.is_one_p ())
1871 12 : switch (m_bit_value.get_value ())
1872 : {
1873 0 : default:
1874 0 : gcc_unreachable ();
1875 4 : case tristate::TS_UNKNOWN:
1876 4 : pp_string (pp, "unknown bit");
1877 4 : break;
1878 4 : case tristate::TS_TRUE:
1879 4 : pp_string (pp, "true bit");
1880 4 : break;
1881 4 : case tristate::TS_FALSE:
1882 4 : pp_string (pp, "false bit");
1883 4 : break;
1884 : }
1885 : else
1886 351 : switch (m_bit_value.get_value ())
1887 : {
1888 0 : default:
1889 0 : gcc_unreachable ();
1890 152 : case tristate::TS_UNKNOWN:
1891 152 : pp_string (pp, "unknown bits");
1892 152 : break;
1893 16 : case tristate::TS_TRUE:
1894 16 : pp_string (pp, "true bits");
1895 16 : break;
1896 183 : case tristate::TS_FALSE:
1897 183 : pp_string (pp, "false bits");
1898 183 : break;
1899 : }
1900 363 : }
1901 :
1902 : void
1903 363 : tristate_bit_vector::add_dump_widget_children (text_art::tree_widget &,
1904 : node_dump_state &) const
1905 : {
1906 : // no-op
1907 363 : }
1908 :
1909 : void
1910 1859495 : tristate_bit_vector::accept_node_visitor (node_visitor &v) const
1911 : {
1912 1859495 : v.visit_bit_vector (*this);
1913 1859495 : }
1914 :
1915 : std::unique_ptr<json::object>
1916 40 : tristate_bit_vector::to_json () const
1917 : {
1918 40 : auto obj = bit_vector::make_json_obj ("tristate_bit_vector");
1919 40 : obj->set_string ("bit_value", m_bit_value.as_string ());
1920 40 : return obj;
1921 : }
1922 :
1923 : std::unique_ptr<diagnostics::markup::node>
1924 0 : tristate_bit_vector::make_markup_node (markup_context &) const
1925 : {
1926 0 : return diagnostics::markup::make_text_node ("tristate_bit_vector");
1927 : }
1928 :
1929 : iter_result
1930 1925 : tristate_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
1931 : void *user_data),
1932 : void *) const
1933 : {
1934 1925 : return iter_result::keep_going;
1935 : }
1936 :
1937 : /* tristate(x)[m..n] --> tristate(x, sizeof(m..n)). */
1938 :
1939 : const bit_vector *
1940 252652 : tristate_bit_vector::
1941 : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
1942 : {
1943 252652 : return &m_bv_mgr.get_tristate_bits (bits_to_use.get_size (),
1944 252652 : get_bit_value ());
1945 : }
1946 :
1947 : /* symbolic::bit_vector consolidation. */
1948 :
1949 4409 : bit_vector_manager::bit_vector_manager (node_manager &node_mgr)
1950 4409 : : m_node_mgr (node_mgr),
1951 4409 : m_empty_bv (*this)
1952 : {
1953 : // Populate m_cached_bytes
1954 4409 : memset (m_cached_bytes, 0, sizeof (m_cached_bytes));
1955 4409 : m_cached_bytes[0x00] = &get_all_zeros (1_byte);
1956 1124295 : for (int i = 1; i < 255; ++i)
1957 : {
1958 1119886 : auto &rmm = node_mgr.get_region_model_manager ();
1959 1119886 : auto &sval = *rmm.get_or_create_int_cst (unsigned_char_type_node, i);
1960 1119886 : m_cached_bytes[i] = &get_bit_vector_from_svalue (sval);
1961 : }
1962 4409 : m_cached_bytes[0xff] = &get_all_ones (1_byte);
1963 4409 : }
1964 :
1965 :
1966 : const bit_vector &
1967 634391 : bit_vector_manager::get_tristate_bits (const symbolic_bit_size &num_bits,
1968 : tristate bit_val)
1969 : {
1970 634391 : if (num_bits.is_zero_p ())
1971 4 : return m_empty_bv;
1972 :
1973 634387 : const symbolic::tristate_bit_vector::key k {num_bits, bit_val};
1974 634387 : auto iter = m_tristate_map.find (k);
1975 634387 : if (iter != m_tristate_map.end ())
1976 614946 : return *(iter->second);
1977 19441 : auto bv_up = std::make_unique<symbolic::tristate_bit_vector> (*this, k);
1978 19441 : auto &result = *bv_up.get ();
1979 19441 : m_tristate_map.insert ({k, std::move (bv_up)});
1980 19441 : return result;
1981 19441 : }
1982 :
1983 : const bit_vector &
1984 268758 : bit_vector_manager::get_tristate_bits (const concrete_bit_size &num_bits,
1985 : tristate bit_val)
1986 : {
1987 268758 : return get_tristate_bits (symbolic_from_concrete (num_bits,
1988 : get_bit_manager ()),
1989 268758 : bit_val);
1990 : }
1991 :
1992 : // Unknown bits of unknown length
1993 : const bit_vector &
1994 326 : bit_vector_manager::get_unknown_bits ()
1995 : {
1996 326 : const symbolic_bit_size &unknown_size = get_bit_manager ().get_unknown ();
1997 326 : return get_tristate_bits (unknown_size, tristate::unknown ());
1998 : }
1999 :
2000 : static void
2001 2275453 : append_canonically (std::vector<const bit_vector *> &canonical_bvs,
2002 : const bit_vector &bv_to_add,
2003 : bit_vector_manager &bv_mgr)
2004 : {
2005 2275453 : if (bv_to_add.get_size ().is_zero_p ())
2006 : return;
2007 :
2008 : /* Flatten adding concat bit_vectors. */
2009 2275437 : if (auto concat_bv = bv_to_add.dyn_cast_concat_bit_vector ())
2010 : {
2011 184 : for (auto iter : *concat_bv)
2012 128 : append_canonically (canonical_bvs, *iter, bv_mgr);
2013 : return;
2014 : }
2015 :
2016 2275381 : if (!canonical_bvs.empty ())
2017 : {
2018 : /* Check for merging opportunities. */
2019 41876 : auto &back = canonical_bvs.back ();
2020 41876 : gcc_assert (back);
2021 :
2022 : /* A + A --> A * 2 */
2023 41876 : if (&bv_to_add == back)
2024 : {
2025 821 : back = &bv_mgr.get_repeated_bits (bv_to_add, 2);
2026 821 : return;
2027 : }
2028 :
2029 : /* (A * n) + A --> A * (n + 1). */
2030 41055 : if (auto repeated_bv = back->dyn_cast_repeated_bit_vector ())
2031 787 : if (&repeated_bv->get_inner_bit_vector () == &bv_to_add)
2032 : {
2033 17 : auto &unitless_mgr
2034 17 : = bv_mgr.get_node_manager ().get_scalars ().get_unitless ();
2035 34 : back = &bv_mgr.get_repeated_bits
2036 17 : (repeated_bv->get_inner_bit_vector (),
2037 17 : (repeated_bv->get_repeat_count ()
2038 17 : + unitless_mgr.get_concrete (1)));
2039 17 : return;
2040 : }
2041 :
2042 : /* A + (A * n) --> A * (n + 1). */
2043 41038 : if (auto repeated_bv = bv_to_add.dyn_cast_repeated_bit_vector ())
2044 708 : if (back == &repeated_bv->get_inner_bit_vector ())
2045 : {
2046 4 : auto &unitless_mgr
2047 4 : = bv_mgr.get_node_manager ().get_scalars ().get_unitless ();
2048 8 : back = &bv_mgr.get_repeated_bits
2049 4 : (repeated_bv->get_inner_bit_vector (),
2050 4 : (repeated_bv->get_repeat_count ()
2051 4 : + unitless_mgr.get_concrete (1)));
2052 4 : return;
2053 : }
2054 :
2055 : /* (A * m) + (A * n) --> A * (m + n). */
2056 41034 : if (auto repeated_lhs = back->dyn_cast_repeated_bit_vector ())
2057 770 : if (auto repeated_rhs = bv_to_add.dyn_cast_repeated_bit_vector ())
2058 166 : if (&repeated_lhs->get_inner_bit_vector ()
2059 166 : == &repeated_rhs->get_inner_bit_vector ())
2060 : {
2061 4 : back = &bv_mgr.get_repeated_bits
2062 4 : (repeated_lhs->get_inner_bit_vector (),
2063 4 : (repeated_lhs->get_repeat_count ()
2064 4 : + repeated_rhs->get_repeat_count ()));
2065 4 : return;
2066 : }
2067 :
2068 : /* concat(A[p, q], A[q, r]) --> A[p, r]. */
2069 41030 : if (auto cropped_lhs = back->dyn_cast_cropped_bit_vector ())
2070 359 : if (auto cropped_rhs = bv_to_add.dyn_cast_cropped_bit_vector ())
2071 52 : if ((&cropped_lhs->get_uncropped_bit_vector ()
2072 52 : == &cropped_rhs->get_uncropped_bit_vector ())
2073 52 : && (&cropped_lhs->get_uncropped_bits_to_use ().get_next_offset ()
2074 17 : == &cropped_rhs->get_uncropped_bits_to_use ().get_start_offset ()))
2075 : {
2076 9 : symbolic_bit_range concat_bit_range
2077 9 : (cropped_lhs->get_uncropped_bits_to_use ().get_start_offset (),
2078 9 : cropped_lhs->get_size () + cropped_rhs->get_size ());
2079 9 : back = &bv_mgr.get_cropped_bits (cropped_lhs->get_uncropped_bit_vector (),
2080 : concat_bit_range);
2081 9 : return;
2082 : }
2083 :
2084 : /* poisoned(m, X) + poisoned(n, X) --> poisoned(m + n, X)
2085 : for same kind of poison. */
2086 41021 : if (auto poisoned_lhs = back->dyn_cast_poisoned_bit_vector ())
2087 421 : if (auto poisoned_rhs = bv_to_add.dyn_cast_poisoned_bit_vector ())
2088 47 : if (poisoned_lhs->get_poison_kind () == poisoned_rhs->get_poison_kind ())
2089 : {
2090 86 : back = &bv_mgr.get_poisoned_bits
2091 43 : ((poisoned_lhs->get_size ()
2092 43 : + poisoned_rhs->get_size ()),
2093 : poisoned_lhs->get_poison_kind ());
2094 43 : return;
2095 : }
2096 :
2097 : /* tristate(m, X) + tristate(n, X) --> tristate(m + n, X). */
2098 40978 : if (auto tristate_lhs = back->dyn_cast_tristate_bit_vector ())
2099 4302 : if (auto tristate_rhs = bv_to_add.dyn_cast_tristate_bit_vector ())
2100 1692 : if (tristate_lhs->get_bit_value () == tristate_rhs->get_bit_value ())
2101 : {
2102 1339 : back = &bv_mgr.get_tristate_bits
2103 1339 : ((tristate_lhs->get_size ()
2104 1339 : + tristate_rhs->get_size ()),
2105 : tristate_lhs->get_bit_value ());
2106 1339 : return;
2107 : }
2108 :
2109 : /* bits_from_ubc (BC, R1) + bits_from_ubc (BC, R2)
2110 : --> bits_from_ubc (BC, R1 + R2)
2111 : if it's the same BC and the ranges touch. */
2112 39639 : if (auto from_ubc_lhs = back->dyn_cast_bit_vector_from_ubc ())
2113 455 : if (auto from_ubc_rhs = bv_to_add.dyn_cast_bit_vector_from_ubc ())
2114 27 : if (&from_ubc_lhs->get_bit_contents ()
2115 27 : == &from_ubc_rhs->get_bit_contents ())
2116 15 : if (&from_ubc_lhs->get_bit_range ().get_next_offset ()
2117 15 : == &from_ubc_rhs->get_bit_range ().get_start_offset ())
2118 : {
2119 11 : symbolic_bit_range combined_bit_range
2120 11 : (from_ubc_lhs->get_bit_range ().get_start_offset (),
2121 11 : (from_ubc_lhs->get_bit_range ().get_size ()
2122 11 : + from_ubc_rhs->get_bit_range ().get_size ()));
2123 11 : auto &ubc = from_ubc_lhs->get_bit_contents ();
2124 11 : back = &ubc.get_bits (combined_bit_range);
2125 11 : return;
2126 : }
2127 : }
2128 :
2129 2273133 : canonical_bvs.push_back (&bv_to_add);
2130 : }
2131 :
2132 : /* Simplify BIT_VECTORS into a canonical form. */
2133 :
2134 : std::vector<const bit_vector *>
2135 2233509 : bit_vector_manager::
2136 : canonicalize_concat_bits (const std::vector<const bit_vector *> &bvs)
2137 : {
2138 2233509 : std::vector<const bit_vector *> result;
2139 4508834 : for (auto iter : bvs)
2140 2275325 : append_canonically (result, *iter, *this);
2141 2233509 : return result;
2142 : }
2143 :
2144 : const bit_vector *
2145 2233505 : bit_vector_manager::
2146 : maybe_fold_concat_bits (const std::vector<const bit_vector *> &canonical_bvs)
2147 : {
2148 : /* Unwrap single element: concat(X) --> X. */
2149 2233505 : if (canonical_bvs.size () == 1)
2150 2196641 : return canonical_bvs[0];
2151 :
2152 : return nullptr;
2153 : }
2154 :
2155 : const bit_vector &
2156 2233512 : bit_vector_manager::
2157 : get_concat_bits (std::vector<const bit_vector *> bvs)
2158 : {
2159 2233512 : if (bvs.size () == 0)
2160 3 : return m_empty_bv;
2161 :
2162 : /* Simplify into a canonical form. */
2163 2233509 : auto canonical_bvs = canonicalize_concat_bits (bvs);
2164 2233509 : if (canonical_bvs.size () == 0)
2165 4 : return m_empty_bv;
2166 :
2167 2233505 : if (auto *folded = maybe_fold_concat_bits (canonical_bvs))
2168 : return *folded;
2169 :
2170 36864 : const symbolic::concat_bit_vector::key k (std::move (canonical_bvs));
2171 36864 : auto iter = m_concat_map.find (k);
2172 36864 : if (iter != m_concat_map.end ())
2173 32755 : return *(iter->second);
2174 :
2175 4109 : auto bv_up = std::make_unique<symbolic::concat_bit_vector> (*this, k);
2176 4109 : auto &result = *bv_up.get ();
2177 4109 : m_concat_map.insert ({k, std::move (bv_up)});
2178 4109 : return result;
2179 2274482 : }
2180 :
2181 : const bit_vector &
2182 26132 : bit_vector_manager::get_conjured_bits (const gimple *stmt,
2183 : const region *id_reg,
2184 : const conjured_purge &p,
2185 : unsigned idx)
2186 : {
2187 26132 : const symbolic::conjured_bit_vector::key k (stmt, id_reg, idx);
2188 26132 : auto iter = m_conjured_map.find (k);
2189 26132 : if (iter != m_conjured_map.end ())
2190 : {
2191 11572 : auto &bv = iter->second;
2192 : /* We're reusing an existing conjured_bit_vector, perhaps from a different
2193 : state within this analysis, or perhaps from an earlier state on this
2194 : execution path. For the latter, purge any state involving the "new"
2195 : bit_vector from the current program_state. */
2196 11572 : p.purge (*bv);
2197 11572 : return *bv;
2198 : }
2199 14560 : auto bv_up = std::make_unique<symbolic::conjured_bit_vector> (*this, k);
2200 14560 : auto &result = *bv_up.get ();
2201 14560 : m_conjured_map.insert ({k, std::move (bv_up)});
2202 14560 : return result;
2203 14560 : }
2204 :
2205 : const bit_vector *
2206 1338349 : bit_vector_manager::maybe_fold_bits_for_constant (tree tree_cst)
2207 : {
2208 1338349 : gcc_assert (tree_cst);
2209 :
2210 1338349 : switch (TREE_CODE (tree_cst))
2211 : {
2212 : default:
2213 : break;
2214 :
2215 1337082 : case INTEGER_CST:
2216 1337082 : {
2217 1337082 : bit_size_t size;
2218 1337082 : bool got_size = int_size_in_bits (TREE_TYPE (tree_cst), &size);
2219 1337082 : gcc_assert (got_size);
2220 :
2221 1337082 : integer_with_unit<units::bit> num_bits = convert_from_bit_size_t (size);
2222 :
2223 : /* Fold all-zeroes and all-ones. */
2224 1337082 : if (zerop (tree_cst))
2225 115716 : return &get_all_zeros (num_bits);
2226 1221366 : if (integer_all_onesp (tree_cst))
2227 10484 : return &get_all_ones (num_bits);
2228 :
2229 : /* Fold bytes. */
2230 1210882 : if (num_bits == 8_bits)
2231 : {
2232 1120274 : uint8_t val = TREE_INT_CST_LOW (tree_cst);
2233 1120274 : if (auto *b = m_cached_bytes[val])
2234 : return b;
2235 : }
2236 130906 : }
2237 1206176 : break;
2238 :
2239 42 : case RAW_DATA_CST:
2240 42 : if (RAW_DATA_LENGTH (tree_cst) == 0)
2241 4 : return &m_empty_bv;
2242 : break;
2243 : }
2244 : return nullptr;
2245 : }
2246 :
2247 : const bit_vector &
2248 120 : bit_vector_manager::get_bits_for_constant (tree tree_cst)
2249 : {
2250 120 : if (auto *folded = maybe_fold_bits_for_constant (tree_cst))
2251 : return *folded;
2252 :
2253 48 : const svalue *sval
2254 48 : = get_svalue_manager ().get_or_create_constant_svalue (tree_cst);
2255 48 : return get_bit_vector_from_svalue (*sval);
2256 : }
2257 :
2258 : const bit_vector *
2259 13978 : bit_vector_manager::
2260 : maybe_fold_bytes_within_constant (tree tree_cst,
2261 : concrete_byte_range conc_bytes)
2262 : {
2263 13978 : gcc_assert (tree_cst);
2264 13978 : gcc_assert (CONSTANT_CLASS_P (tree_cst));
2265 27956 : gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
2266 :
2267 13978 : switch (TREE_CODE (tree_cst))
2268 : {
2269 : default:
2270 : return nullptr;
2271 :
2272 : /* Special-case these. */
2273 1821 : case STRING_CST:
2274 3642 : return maybe_fold_bytes_within_string_cst (tree_cst, conc_bytes);
2275 194 : case RAW_DATA_CST:
2276 388 : return maybe_fold_bytes_within_raw_data_cst (tree_cst, conc_bytes);
2277 :
2278 : /* Handle the constants that native_encode_expr can. */
2279 11963 : case INTEGER_CST:
2280 11963 : case REAL_CST:
2281 11963 : case FIXED_CST:
2282 11963 : case COMPLEX_CST:
2283 11963 : case VECTOR_CST:
2284 11963 : case CONSTRUCTOR:
2285 11963 : {
2286 : /* Use native_encode_expr and extract the pertinent byte(s). */
2287 11963 : unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
2288 11963 : int size = native_encode_expr (tree_cst, buf, sizeof buf, 0);
2289 11963 : if (size == 0)
2290 : return nullptr;
2291 :
2292 23926 : gcc_assert (conc_bytes.get_last_offset () < concrete_byte_size (size));
2293 :
2294 11963 : std::vector<const bit_vector *> vec_of_bytes;
2295 11963 : const concrete_byte_offset next_offset = conc_bytes.get_next_offset ();
2296 11963 : for (concrete_byte_offset conc_offset = conc_bytes.get_start_offset ();
2297 24130 : conc_offset < next_offset;
2298 12167 : conc_offset += 1_byte)
2299 12167 : vec_of_bytes.push_back
2300 12167 : (&get_uint8 (buf[conc_offset.as_unsigned_long ()]));
2301 :
2302 11963 : return &get_concat_bits (std::move (vec_of_bytes));
2303 11963 : }
2304 : }
2305 : }
2306 :
2307 : const bit_vector *
2308 1821 : bit_vector_manager::
2309 : maybe_fold_bytes_within_string_cst (tree string_cst,
2310 : concrete_byte_range conc_bytes)
2311 : {
2312 1821 : gcc_assert (TREE_CODE (string_cst) == STRING_CST);
2313 :
2314 : /* Adapted from fold_read_from_constant_string. */
2315 1821 : scalar_int_mode char_mode;
2316 1821 : if (!is_int_mode (TYPE_MODE (TREE_TYPE (TREE_TYPE (string_cst))),
2317 : &char_mode))
2318 : return nullptr;
2319 3642 : if (GET_MODE_SIZE (char_mode) != 1)
2320 : return nullptr;
2321 :
2322 3642 : gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
2323 3642 : if (conc_bytes.get_start_offset ()
2324 3642 : < integer_with_unit<units::byte> (TREE_STRING_LENGTH (string_cst)))
2325 : {
2326 : /* We're within the area defined by TREE_STRING_POINTER. */
2327 1814 : if (conc_bytes.get_size () == 1_byte)
2328 1496 : return &get_uint8
2329 2992 : (TREE_STRING_POINTER (string_cst)
2330 3487 : [conc_bytes.get_start_offset ().get_integer ().as_unsigned_long ()]);
2331 : else
2332 : return nullptr;
2333 : }
2334 : else
2335 : {
2336 : /* We're in the padding area of trailing zeroes. */
2337 7 : return &get_all_zeros (conc_bytes.get_size ());
2338 : }
2339 : }
2340 :
2341 : const bit_vector *
2342 194 : bit_vector_manager::
2343 : maybe_fold_bytes_within_raw_data_cst (tree raw_data_cst,
2344 : concrete_byte_range conc_bytes)
2345 : {
2346 194 : gcc_assert (TREE_CODE (raw_data_cst) == RAW_DATA_CST);
2347 :
2348 194 : if (conc_bytes.get_size () != 1_byte)
2349 : return nullptr;
2350 :
2351 388 : gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
2352 388 : gcc_assert
2353 : (conc_bytes.get_start_offset ()
2354 : < integer_with_unit<units::byte> (RAW_DATA_LENGTH (raw_data_cst)));
2355 :
2356 194 : size_t idx
2357 230 : = conc_bytes.get_start_offset ().get_integer ().as_unsigned_long ();
2358 194 : return &get_uint8 (RAW_DATA_UCHAR_ELT (raw_data_cst, idx));
2359 : }
2360 :
2361 : const bit_vector &
2362 22192 : bit_vector_manager::
2363 : make_baseline_bit_vector (baseline_key k)
2364 : {
2365 22192 : gcc_assert (k.m_base_reg->can_have_initial_svalue_p ());
2366 :
2367 22192 : auto &rmm = m_node_mgr.get_svalue_manager ();
2368 22192 : const svalue *sval = nullptr;
2369 22192 : switch (k.m_baseline_state)
2370 : {
2371 0 : default:
2372 0 : gcc_unreachable ();
2373 :
2374 816 : case baseline_state::main:
2375 816 : sval = k.m_base_reg->get_initial_value_at_main (&rmm);
2376 816 : break;
2377 :
2378 21376 : case baseline_state::after_main:
2379 21376 : sval = rmm.get_or_create_initial_value (k.m_base_reg);
2380 21376 : break;
2381 : }
2382 :
2383 22192 : gcc_assert (sval);
2384 22192 : return get_bit_vector_from_svalue (*sval);
2385 : }
2386 :
2387 : const bit_vector &
2388 22192 : bit_vector_manager::
2389 : get_baseline_bit_vector (const region &base_reg,
2390 : baseline_state bs)
2391 : {
2392 22192 : baseline_key k {&base_reg, bs};
2393 22192 : auto iter = m_baseline_map.find (k);
2394 22192 : if (iter != m_baseline_map.end ())
2395 0 : return iter->second;
2396 :
2397 22192 : auto &bc = make_baseline_bit_vector (k);
2398 22192 : m_baseline_map.insert ({k, bc});
2399 22192 : return bc;
2400 : }
2401 :
2402 : const bit_vector *
2403 2662943 : bit_vector_manager::
2404 : maybe_fold_cropped_bits (const bit_vector &inner_bv,
2405 : const symbolic_bit_range &inner_bits_to_use)
2406 : {
2407 2662943 : if (inner_bits_to_use.get_size ().is_zero_p ())
2408 4 : return &m_empty_bv;
2409 :
2410 : // x[0..size(x)] --> x. */
2411 2662939 : if (inner_bits_to_use.get_start_offset ().is_zero_p ()
2412 2662939 : && &inner_bits_to_use.get_size () == &inner_bv.get_size ())
2413 : return &inner_bv;
2414 :
2415 496449 : if (auto folded = inner_bv.maybe_fold_crop (inner_bits_to_use))
2416 : return folded;
2417 :
2418 : return nullptr;
2419 : }
2420 :
2421 : const bit_vector &
2422 2662943 : bit_vector_manager::
2423 : get_cropped_bits (const bit_vector &inner_bv,
2424 : const symbolic_bit_range &inner_bits_to_use)
2425 : {
2426 2662943 : if (auto *folded = maybe_fold_cropped_bits (inner_bv, inner_bits_to_use))
2427 : return *folded;
2428 :
2429 87570 : const symbolic::cropped_bit_vector::key k {&inner_bv,
2430 87570 : inner_bits_to_use};
2431 87570 : auto iter = m_cropped_map.find (k);
2432 87570 : if (iter != m_cropped_map.end ())
2433 80203 : return *(iter->second);
2434 7367 : auto bv_up = std::make_unique<cropped_bit_vector> (*this, k);
2435 7367 : auto &result = *bv_up.get ();
2436 7367 : m_cropped_map.insert ({k, std::move (bv_up)});
2437 7367 : return result;
2438 7367 : }
2439 :
2440 : const bit_vector &
2441 475598 : bit_vector_manager::
2442 : get_cropped_bytes (const bit_vector &inner_bv,
2443 : const symbolic_byte_range &inner_bytes_to_use)
2444 : {
2445 475598 : return get_cropped_bits (inner_bv,
2446 475598 : bits_from_bytes (inner_bytes_to_use));
2447 : }
2448 :
2449 : const bit_vector *
2450 3144 : bit_vector_manager::
2451 : maybe_fold_repeated_bits (const bit_vector &inner_bv,
2452 : const symbolic_integer &repeat_count)
2453 : {
2454 3144 : if (repeat_count.is_zero_p ())
2455 4 : return &m_empty_bv;
2456 :
2457 3140 : if (repeat_count.is_one_p ())
2458 : return &inner_bv;
2459 :
2460 1643 : if (auto poisoned_bv = inner_bv.dyn_cast_poisoned_bit_vector ())
2461 42 : return &get_poisoned_bits
2462 42 : (inner_bv.get_size () * repeat_count,
2463 42 : poisoned_bv->get_poison_kind ());
2464 :
2465 1601 : if (auto tristate_bv = inner_bv.dyn_cast_tristate_bit_vector ())
2466 953 : return &get_tristate_bits
2467 953 : (inner_bv.get_size () * repeat_count,
2468 953 : tristate_bv->get_bit_value ());
2469 :
2470 648 : if (auto repeated_bv = inner_bv.dyn_cast_repeated_bit_vector ())
2471 11 : return &get_repeated_bits (repeated_bv->get_inner_bit_vector (),
2472 11 : (repeated_bv->get_repeat_count ()
2473 11 : * repeat_count));
2474 :
2475 : return nullptr;
2476 : }
2477 :
2478 : const bit_vector &
2479 3144 : bit_vector_manager::
2480 : get_repeated_bits (const bit_vector &inner_bv,
2481 : const symbolic_integer &repeat_count)
2482 : {
2483 3144 : if (auto *folded = maybe_fold_repeated_bits (inner_bv, repeat_count))
2484 : return *folded;
2485 :
2486 637 : const symbolic::repeated_bit_vector::key k {&inner_bv, &repeat_count};
2487 637 : auto iter = m_repeated_map.find (k);
2488 637 : if (iter != m_repeated_map.end ())
2489 343 : return *(iter->second);
2490 294 : auto bv_up = std::make_unique<repeated_bit_vector> (*this, k);
2491 294 : auto &result = *bv_up.get ();
2492 294 : m_repeated_map.insert ({k, std::move (bv_up)});
2493 294 : return result;
2494 294 : }
2495 :
2496 : const bit_vector &
2497 2421 : bit_vector_manager::
2498 : get_repeated_bits (const bit_vector &inner_bv,
2499 : const concrete_integer &repeat_count)
2500 : {
2501 2421 : auto &integer_mgr = get_node_manager ().get_scalars ().get_unitless ();
2502 2421 : return get_repeated_bits (inner_bv,
2503 2421 : integer_mgr.get_concrete (repeat_count));
2504 : }
2505 :
2506 : /* Return true if TYPE_A and TYPE_B are known to be the same size. */
2507 :
2508 : static bool
2509 14143 : types_are_same_size_p (const_tree type_a, const_tree type_b)
2510 : {
2511 14143 : concrete_bit_size size_a;
2512 14143 : if (!get_type_size (type_a, &size_a))
2513 : return false;
2514 14143 : concrete_bit_size size_b;
2515 14143 : if (!get_type_size (type_b, &size_b))
2516 : return false;
2517 14143 : return size_a == size_b;
2518 14143 : }
2519 :
2520 : const bit_vector *
2521 1806655 : bit_vector_manager::maybe_fold_bits_for_svalue (const svalue &sval)
2522 : {
2523 1806655 : switch (sval.get_kind ())
2524 : {
2525 : default:
2526 : break;
2527 :
2528 1338229 : case SK_CONSTANT:
2529 1338229 : {
2530 1338229 : tree tree_cst = sval.maybe_get_constant ();
2531 1338229 : if (auto *folded = maybe_fold_bits_for_constant (tree_cst))
2532 130860 : return folded;
2533 :
2534 : /* Fold any 1-byte constants we missed. */
2535 1207391 : auto &bit_mgr = get_node_manager ().get_scalars ().get_bits ();
2536 1207391 : concrete_bit_size conc_bit_size;
2537 1207391 : if (sval.has_concrete_size_p (&conc_bit_size, bit_mgr)
2538 3622173 : && conc_bit_size == 8_bits)
2539 : {
2540 1115590 : unsigned char buf[1];
2541 1115590 : int size = native_encode_expr (tree_cst, buf, sizeof buf, 0);
2542 1115590 : gcc_assert (size == 1);
2543 1115590 : unsigned char val = buf[0];
2544 1115590 : if (auto *b = m_cached_bytes[val])
2545 22 : return b;
2546 : }
2547 22 : }
2548 1207369 : break;
2549 :
2550 : /* TODO: re-enabling this will require a rewrite of parts of
2551 : access-diagram.cc which expect string regions, rather than
2552 : constant_svalue of string_cst. */
2553 : #if 0
2554 : case SK_INITIAL:
2555 : {
2556 : auto &init_sval = *as_a <const initial_svalue *> (&sval);
2557 : if (auto *string_reg
2558 : = init_sval.get_region ()->dyn_cast_string_region ())
2559 : return &get_bits_for_constant (string_reg->get_string_cst ());
2560 : }
2561 : break;
2562 : #endif
2563 :
2564 70446 : case SK_BIT_VECTOR:
2565 70446 : {
2566 70446 : auto &bit_vector_sval = *as_a<const svalue_from_bit_vector *> (&sval);
2567 70446 : return &bit_vector_sval.get_bit_vector ();
2568 : }
2569 119547 : break;
2570 :
2571 119547 : case SK_UNKNOWN:
2572 119547 : {
2573 119547 : concrete_bit_size size;
2574 119547 : if (sval.has_concrete_size_p (&size, get_bit_manager ()))
2575 119547 : return &get_unknown_bits (size);
2576 : else
2577 0 : return &get_unknown_bits ();
2578 119547 : }
2579 20753 : break;
2580 :
2581 20753 : case SK_UNARYOP:
2582 20753 : {
2583 20753 : auto &unaryop_sval = *as_a<const unaryop_svalue *> (&sval);
2584 20753 : if (CONVERT_EXPR_CODE_P (unaryop_sval.get_op ()))
2585 : {
2586 : /* If we have a type conversion for which no instructions
2587 : are needed, they are presumably bit-for-bit identical,
2588 : or for which the sizes are identical.
2589 : Fold away the conversion, so e.g.
2590 : e.g. BIT_VECTOR_FOR (UNARY_OP(signed, NOP_EXPR, SVAL(unsigned)))
2591 : folds to BIT_VECTOR_FOR (SVAL(unsigned)). */
2592 19752 : if (sval.get_type () == nullptr
2593 19752 : || unaryop_sval.get_arg ()->get_type () == nullptr
2594 19744 : || tree_nop_conversion_p (sval.get_type (),
2595 19744 : unaryop_sval.get_arg ()->get_type ())
2596 33895 : || types_are_same_size_p (sval.get_type (),
2597 14143 : unaryop_sval.get_arg ()->get_type ()))
2598 5622 : return &get_bit_vector_from_svalue (*unaryop_sval.get_arg ());
2599 : }
2600 : }
2601 : break;
2602 : }
2603 :
2604 : return nullptr;
2605 : }
2606 :
2607 : const bit_vector &
2608 1786178 : bit_vector_manager::get_bit_vector_from_svalue (const svalue &sval)
2609 : {
2610 1786178 : if (auto *folded = maybe_fold_bits_for_svalue (sval))
2611 : return *folded;
2612 :
2613 : /* We need to be able to determine the size of SVAL. */
2614 1465860 : concrete_bit_size conc_bit_size;
2615 1465860 : gcc_assert (sval.has_concrete_size_p (&conc_bit_size,
2616 : get_bit_manager ()));
2617 :
2618 1465860 : if (conc_bit_size == 0_bits)
2619 0 : return get_empty ();
2620 :
2621 1465860 : const symbolic::bit_vector_from_svalue::key k {&sval};
2622 1465860 : auto iter = m_svalue_to_bv_map.find (k);
2623 1465860 : if (iter != m_svalue_to_bv_map.end ())
2624 286067 : return *(iter->second);
2625 1179793 : auto bv_up = std::make_unique<symbolic::bit_vector_from_svalue> (*this, k);
2626 1179793 : auto &result = *bv_up.get ();
2627 1179793 : m_svalue_to_bv_map.insert ({k, std::move (bv_up)});
2628 1179793 : return result;
2629 2645653 : }
2630 :
2631 : const bit_vector *
2632 1022 : bit_vector_manager::maybe_get_bit_vector_from_svalue (const svalue &sval)
2633 : {
2634 1022 : if (auto *folded = maybe_fold_bits_for_svalue (sval))
2635 : return folded;
2636 :
2637 1019 : const symbolic::bit_vector_from_svalue::key k {&sval};
2638 1019 : auto iter = m_svalue_to_bv_map.find (k);
2639 1019 : if (iter != m_svalue_to_bv_map.end ())
2640 1019 : return iter->second.get ();
2641 : return nullptr;
2642 : }
2643 :
2644 : const bit_vector &
2645 1664124 : bit_vector_manager::get_poisoned_bits (const symbolic_bit_size &num_bits,
2646 : enum poison_kind kind)
2647 : {
2648 1664124 : if (num_bits.is_zero_p ())
2649 23 : return m_empty_bv;
2650 :
2651 1664101 : poisoned_bit_vector::key k {num_bits, kind};
2652 :
2653 1664101 : auto iter = m_poisoned_map.find (k);
2654 1664101 : if (iter != m_poisoned_map.end ())
2655 1651665 : return *(iter->second);
2656 :
2657 12436 : auto bv_up = std::make_unique<poisoned_bit_vector> (*this, k);
2658 12436 : auto &result = *bv_up.get ();
2659 12436 : m_poisoned_map.insert ({k, std::move (bv_up)});
2660 12436 : return result;
2661 12436 : }
2662 :
2663 : const bit_vector &
2664 56 : bit_vector_manager::get_poisoned_bits (const concrete_bit_size &num_bits,
2665 : enum poison_kind kind)
2666 : {
2667 56 : return get_poisoned_bits (symbolic_from_concrete (num_bits,
2668 : get_bit_manager ()),
2669 56 : kind);
2670 : }
2671 :
2672 : #if CHECKING_P
2673 :
2674 : const bit_vector &
2675 128 : bit_vector_manager::
2676 : get_named_test_bit_vector (const symbolic_bit_size &size_in_bits,
2677 : std::string label)
2678 : {
2679 128 : auto bv_up = std::make_unique<named_test_bit_vector> (*this,
2680 : size_in_bits,
2681 128 : std::move (label));
2682 128 : auto &result = *bv_up.get ();
2683 128 : m_named_test_bvs.push_back (std::move (bv_up));
2684 256 : return result;
2685 128 : }
2686 :
2687 : const bit_vector &
2688 12 : bit_vector_manager::
2689 : get_named_test_bit_vector (const symbolic_byte_size &size_in_bytes,
2690 : std::string label)
2691 : {
2692 12 : auto &size_in_bits = bits_from_bytes (size_in_bytes);
2693 12 : return get_named_test_bit_vector (size_in_bits, std::move (label));
2694 : }
2695 :
2696 : const bit_vector &
2697 116 : bit_vector_manager::
2698 : get_named_test_bit_vector (const concrete_bit_size &conc_size_in_bits,
2699 : std::string label)
2700 : {
2701 116 : auto &bit_mgr = get_node_manager ().get_scalars ().get_bits ();
2702 116 : auto &sym_size_in_bits = symbolic_from_concrete (conc_size_in_bits, bit_mgr);
2703 116 : return get_named_test_bit_vector (sym_size_in_bits, std::move (label));
2704 : }
2705 :
2706 : const bit_vector &
2707 100 : bit_vector_manager::
2708 : get_named_test_bit_vector (const concrete_byte_size &conc_size_in_bytes,
2709 : std::string label)
2710 : {
2711 100 : concrete_bit_size conc_size_in_bits = bits_from_bytes (conc_size_in_bytes);
2712 100 : return get_named_test_bit_vector (conc_size_in_bits, std::move (label));
2713 100 : }
2714 :
2715 : #endif /* #if CHECKING_P */
2716 :
2717 : } // namespace ana::symbolic
2718 :
2719 : #if CHECKING_P
2720 :
2721 : namespace selftest {
2722 :
2723 : static void
2724 4 : test_maybe_set_irange_bitmask_from_concrete_tristate_vector ()
2725 : {
2726 : /* A combination of ones, zeros, and unknown, expressed in order
2727 : LSB through MSB. */
2728 4 : concrete_tristate_vector ts_vec
2729 : ({tristate (true),
2730 : tristate (false),
2731 4 : tristate::unknown (),
2732 : tristate (true),
2733 4 : tristate (false)});
2734 :
2735 4 : irange_bitmask irange_bmask;
2736 4 : bool ok = symbolic::maybe_set_irange_bitmask_from_concrete_tristate_vector
2737 4 : (ts_vec, &irange_bmask);
2738 4 : ASSERT_TRUE (ok);
2739 4 : irange_bmask.verify_mask ();
2740 :
2741 : /* We expect:
2742 : index: [..., 4, 3, 2, 1, 0]
2743 : VALUE: [..., 0, 1, 0, 0, 1]
2744 : MASK: [..., 0, 0, 1, 0, 0]
2745 : | ^ ^ ^ ^ ^
2746 : | | | | | bit 0: true
2747 : | | | | bit 1: false
2748 : | | | bit 2: unknown
2749 : | | bit 3: true
2750 : | bit 4: false. */
2751 4 : ASSERT_EQ (irange_bmask.value (), wi::uhwi (0b01001, 5));
2752 4 : }
2753 :
2754 : static void
2755 4 : test_tristate ()
2756 : {
2757 4 : symbolic::node_manager node_mgr;
2758 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
2759 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2760 :
2761 4 : auto &false_bit = mgr.get_all_zeros (1_bit);
2762 4 : ASSERT_SAME_SYMBOLIC_NODE (false_bit.get_size (),
2763 : bit_mgr.get_concrete (1_bit));
2764 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2765 : (false_bit,
2766 : "tristate_bit_vector[size: 1 bit]: false bit\n");
2767 4 : false_bit.to_json ();
2768 4 : ASSERT_EQ (false_bit.get_tristate_at_offset (0_bits), tristate (false));
2769 :
2770 4 : auto &true_bit = mgr.get_tristate_bits (1_bit, tristate (true));
2771 4 : ASSERT_SAME_SYMBOLIC_NODE (true_bit.get_size (),
2772 : bit_mgr.get_concrete (1_bit));
2773 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2774 : (true_bit,
2775 : "tristate_bit_vector[size: 1 bit]: true bit\n");
2776 4 : true_bit.to_json ();
2777 4 : ASSERT_EQ (true_bit.get_tristate_at_offset (0_bits), tristate (true));
2778 :
2779 4 : auto &unknown_bit = mgr.get_unknown_bits (1_bit);
2780 4 : ASSERT_SAME_SYMBOLIC_NODE (unknown_bit.get_size (),
2781 : bit_mgr.get_concrete (1_bit));
2782 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2783 : (unknown_bit,
2784 : "tristate_bit_vector[size: 1 bit]: unknown bit\n");
2785 4 : unknown_bit.to_json ();
2786 4 : ASSERT_EQ (unknown_bit.get_tristate_at_offset (0_bits), tristate::unknown ());
2787 :
2788 4 : auto &three_zero_bits = mgr.get_all_zeros (3_bits);
2789 4 : ASSERT_SAME_SYMBOLIC_NODE (three_zero_bits.get_size (),
2790 : bit_mgr.get_concrete (3_bits));
2791 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2792 : (three_zero_bits,
2793 : "tristate_bit_vector[size: 3 bits]: false bits\n");
2794 :
2795 4 : auto &byte_00 = mgr.get_all_zeros (1_byte);
2796 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2797 : (byte_00,
2798 : "tristate_bit_vector[size: 1 byte]: false bits\n");
2799 :
2800 4 : auto &byte_ff = mgr.get_tristate_bits (8_bits, tristate (true));
2801 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2802 : (byte_ff,
2803 : "tristate_bit_vector[size: 1 byte]: true bits\n");
2804 :
2805 4 : auto &unknown_32_bits = mgr.get_unknown_bits (32_bits);
2806 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2807 : (unknown_32_bits,
2808 : "tristate_bit_vector[size: 4 bytes]: unknown bits\n");
2809 4 : ASSERT_EQ (unknown_32_bits.get_tristate_at_offset (31_bits),
2810 : tristate::unknown ());
2811 :
2812 4 : auto &x = bit_mgr.get_named_test_scalar ("X");
2813 4 : auto &sym_sized_zeros = mgr.get_all_zeros (x);
2814 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2815 : (sym_sized_zeros,
2816 : "tristate_bit_vector[size: X bits]: false bits\n");
2817 4 : ASSERT_SAME_SYMBOLIC_NODE (sym_sized_zeros.get_size (),
2818 : x);
2819 4 : sym_sized_zeros.to_json ();
2820 4 : ASSERT_EQ (sym_sized_zeros.get_tristate_at_offset (0_bits), tristate (false));
2821 4 : ASSERT_EQ (sym_sized_zeros.get_tristate_at_offset (x), tristate (false));
2822 :
2823 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_all_zeros (0_bits),
2824 : mgr.get_empty ());
2825 4 : mgr.get_empty ().to_json ();
2826 :
2827 4 : {
2828 4 : pretty_printer pp;
2829 4 : hexdump_options hexdump_opts;
2830 4 : hexdump_opts.m_show_headings = true;
2831 4 : hexdump_opts.m_show_binary = true;
2832 4 : unknown_32_bits.hexdump_to_pp (&pp, hexdump_opts);
2833 4 : ASSERT_STREQ
2834 : (pp_formatted_text (&pp),
2835 : (" +-----------------------------------+-----------+-----+\n"
2836 : " | Binary | Hex |ASCII|\n"
2837 : "+------------+-----------------------------------+-----------+-----+\n"
2838 : "|[bytes 0..4)|???????? ???????? ???????? ????????|?? ?? ?? ??|???? |\n"
2839 : "+------------+-----------------------------------+-----------+-----+\n"));
2840 4 : }
2841 4 : {
2842 4 : pretty_printer pp;
2843 4 : hexdump_options hexdump_opts;
2844 4 : hexdump_opts.m_show_headings = false;
2845 4 : hexdump_opts.m_show_binary = true;
2846 4 : mgr.get_all_zeros (32_bits).hexdump_to_pp (&pp, hexdump_opts);
2847 4 : ASSERT_STREQ
2848 : (pp_formatted_text (&pp),
2849 : ("+------------+-----------------------------------+-----------+----+\n"
2850 : "|[bytes 0..4)|00000000 00000000 00000000 00000000|00 00 00 00|....|\n"
2851 : "+------------+-----------------------------------+-----------+----+\n"));
2852 4 : }
2853 4 : {
2854 4 : pretty_printer pp;
2855 4 : hexdump_options hexdump_opts;
2856 4 : hexdump_opts.m_show_headings = false;
2857 4 : hexdump_opts.m_show_binary = true;
2858 4 : mgr.get_all_ones (32_bits).hexdump_to_pp (&pp, hexdump_opts);
2859 4 : ASSERT_STREQ
2860 : (pp_formatted_text (&pp),
2861 : ("+------------+-----------------------------------+-----------+----+\n"
2862 : "|[bytes 0..4)|11111111 11111111 11111111 11111111|ff ff ff ff|....|\n"
2863 : "+------------+-----------------------------------+-----------+----+\n"));
2864 4 : }
2865 4 : }
2866 :
2867 : static void
2868 4 : test_integer_constants ()
2869 : {
2870 4 : symbolic::node_manager node_mgr;
2871 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
2872 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2873 :
2874 : // Verify that we fold all zeroes and all ones
2875 :
2876 4 : auto &char_0
2877 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 0));
2878 4 : ASSERT_SAME_SYMBOLIC_NODE (char_0.get_size (),
2879 : bit_mgr.get_concrete (8_bits));
2880 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2881 : (char_0,
2882 : "tristate_bit_vector[size: 1 byte]: false bits\n");
2883 4 : char_0.to_json ();
2884 :
2885 4 : auto &char_0xff
2886 4 : = mgr.get_bits_for_constant (build_int_cst (unsigned_char_type_node,
2887 : 0xff));
2888 4 : ASSERT_SAME_SYMBOLIC_NODE (char_0xff.get_size (),
2889 : bit_mgr.get_concrete (8_bits));
2890 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2891 : (char_0xff,
2892 : "tristate_bit_vector[size: 1 byte]: true bits\n");
2893 4 : char_0xff.to_json ();
2894 :
2895 : // Verify that we handle constants that we can't simplify
2896 :
2897 4 : auto &char_A
2898 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node,
2899 : 'A'));
2900 4 : ASSERT_SAME_SYMBOLIC_NODE (char_A.get_size (),
2901 : bit_mgr.get_concrete (8_bits));
2902 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2903 : (char_A,
2904 : ("bit_vector_from_svalue[size: 1 byte]\n"
2905 : "`- m_sval: 'unsigned char': constant_svalue ('65')\n"));
2906 :
2907 4 : auto &int_42
2908 4 : = mgr.get_bits_for_constant (build_int_cst (uint32_type_node, 42));
2909 4 : ASSERT_SAME_SYMBOLIC_NODE (int_42.get_size (),
2910 : bit_mgr.get_concrete (32_bits));
2911 4 : int_42.to_json ();
2912 :
2913 : // -1 is simplifiable to all ones...
2914 4 : auto &char_minus_one
2915 4 : = mgr.get_bits_for_constant (build_int_cst (signed_char_type_node, -1));
2916 4 : ASSERT_SAME_SYMBOLIC_NODE (char_minus_one.get_size (),
2917 : bit_mgr.get_concrete (8_bits));
2918 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2919 : (char_minus_one,
2920 : "tristate_bit_vector[size: 1 byte]: true bits\n");
2921 :
2922 : // ...but -2 isn't
2923 4 : auto &char_minus_two
2924 4 : = mgr.get_bits_for_constant (build_int_cst (signed_char_type_node,
2925 : -2));
2926 4 : ASSERT_SAME_SYMBOLIC_NODE (char_minus_two.get_size (),
2927 : bit_mgr.get_concrete (8_bits));
2928 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2929 : (char_minus_two,
2930 : ("bit_vector_from_svalue[size: 1 byte]\n"
2931 : "`- m_sval: 'unsigned char': constant_svalue ('254')\n"));
2932 4 : ASSERT_SAME_SYMBOLIC_NODE
2933 : (char_minus_two,
2934 : mgr.get_bits_for_constant (build_int_cst (unsigned_char_type_node,
2935 : 254)));
2936 4 : }
2937 :
2938 : static void
2939 4 : test_bytes ()
2940 : {
2941 4 : symbolic::node_manager node_mgr;
2942 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
2943 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2944 :
2945 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_uint8 (0),
2946 : mgr.get_all_zeros (1_byte));
2947 1020 : for (int i = 0x01; i < 0xff; ++i)
2948 : {
2949 1016 : auto &b = mgr.get_uint8 (i);
2950 1016 : ASSERT_SAME_SYMBOLIC_NODE (b.get_size (),
2951 : bit_mgr.get_concrete (8_bits));
2952 : }
2953 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_uint8 (0xff),
2954 : mgr.get_all_ones (1_byte));
2955 :
2956 1024 : for (int i = 0; i < 0xff; ++i)
2957 : {
2958 1020 : auto &bv = mgr.get_uint8 (i);
2959 1020 : uint8_t val;
2960 1020 : bool out = bv.maybe_as_uint8 (&val);
2961 1020 : ASSERT_TRUE (out);
2962 1020 : ASSERT_EQ (val, i);
2963 9180 : for (int bit_idx = 0; bit_idx < 8; ++bit_idx)
2964 12256 : ASSERT_EQ (bv.get_tristate_at_offset (concrete_bit_offset (bit_idx)),
2965 : tristate (i & (1 << bit_idx)));
2966 : }
2967 4 : }
2968 :
2969 : static void
2970 4 : test_string_constants ()
2971 : {
2972 4 : tree string_cst_ptr = make_string_constant ("abc");
2973 :
2974 4 : symbolic::node_manager node_mgr;
2975 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
2976 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2977 :
2978 4 : auto &abc0 = bv_mgr.get_bits_for_constant (string_cst_ptr);
2979 4 : ASSERT_SAME_SYMBOLIC_NODE (abc0.get_size (),
2980 : bit_mgr.get_concrete (bits_from_bytes (4_bytes)));
2981 4 : abc0.to_json ();
2982 :
2983 4 : {
2984 4 : pretty_printer pp;
2985 4 : abc0.hexdump_to_pp (&pp, hexdump_options ());
2986 4 : ASSERT_STREQ
2987 : (pp_formatted_text (&pp),
2988 : ("+------------+-----------+----+\n"
2989 : "|[bytes 0..4)|61 62 63 00|abc.|\n"
2990 : "+------------+-----------+----+\n"));
2991 4 : }
2992 :
2993 : /* Verify accessing chars within a STRING_CST. */
2994 4 : {
2995 4 : auto &a = abc0.get_byte_at_offset (0_bytes);
2996 4 : ASSERT_SAME_SYMBOLIC_NODE (a, bv_mgr.get_uint8 ('a'));
2997 :
2998 4 : auto &b = abc0.get_byte_at_offset (1_byte);
2999 4 : ASSERT_SAME_SYMBOLIC_NODE (b, bv_mgr.get_uint8 ('b'));
3000 :
3001 4 : auto &c = abc0.get_byte_at_offset (2_bytes);
3002 4 : ASSERT_SAME_SYMBOLIC_NODE (c, bv_mgr.get_uint8 ('c'));
3003 :
3004 4 : auto &term = abc0.get_byte_at_offset (3_bytes);
3005 4 : ASSERT_SAME_SYMBOLIC_NODE (term, bv_mgr.get_uint8 (0));
3006 : }
3007 :
3008 24 : for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
3009 16 : ASSERT_EQ (abc0.scan_for_first_zero_byte (i),
3010 4 : string_scan::found_nul (3_bytes));
3011 :
3012 : /* Example of concatenating known string literals. */
3013 4 : {
3014 4 : const char *hello = "hello";
3015 4 : const char *world = " world!";
3016 4 : tree t_hello = make_string_constant (hello);
3017 4 : tree t_world = make_string_constant (world);
3018 4 : auto &bv_hello = bv_mgr.get_bits_for_constant (t_hello);
3019 4 : auto &bv_world = bv_mgr.get_bits_for_constant (t_world);
3020 4 : auto &concat_bv = bv_mgr.get_concat_bits
3021 12 : ({&bv_hello.get_prefix (concrete_byte_size (strlen (hello))),
3022 8 : &bv_world.get_prefix (concrete_byte_size (strlen (world))),
3023 4 : &bv_mgr.get_uint8 (0)});
3024 4 : pretty_printer pp;
3025 4 : hexdump_options hexdump_opts;
3026 4 : hexdump_opts.m_bytes_per_line = 8_bytes;
3027 4 : concat_bv.hexdump_to_pp (&pp, hexdump_opts);
3028 4 : ASSERT_STREQ
3029 : (pp_formatted_text (&pp),
3030 : "+-------------+-----------------------+--------+\n"
3031 : "| [bytes 0..8)|68 65 6c 6c 6f 20 77 6f|hello wo|\n"
3032 : "+-------------+-----------------------+--------+\n"
3033 : "|[bytes 8..13)|72 6c 64 21 00 |rld!. |\n"
3034 : "+-------------+-----------------------+--------+\n");
3035 60 : for (concrete_byte_offset i = 0_bytes; i < 13_bytes; ++i)
3036 52 : ASSERT_EQ (concat_bv.scan_for_first_zero_byte (i),
3037 4 : string_scan::found_nul (12_bytes));
3038 4 : }
3039 4 : }
3040 :
3041 : static tree
3042 12 : make_raw_data_constant (const char *buf, size_t size)
3043 : {
3044 12 : tree node = make_node (RAW_DATA_CST);
3045 12 : TREE_TYPE (node) = integer_type_node;
3046 12 : RAW_DATA_LENGTH (node) = size;
3047 12 : RAW_DATA_POINTER (node) = buf;
3048 12 : return node;
3049 : }
3050 :
3051 : static void
3052 4 : test_raw_data_constant_1 ()
3053 : {
3054 4 : tree raw_data_cst_ptr = make_raw_data_constant ("abc", 3);
3055 :
3056 4 : symbolic::node_manager node_mgr;
3057 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3058 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3059 :
3060 4 : auto &abc = mgr.get_bits_for_constant (raw_data_cst_ptr);
3061 4 : ASSERT_SAME_SYMBOLIC_NODE (abc.get_size (),
3062 : bit_mgr.get_concrete (bits_from_bytes (3_bytes)));
3063 4 : abc.to_json ();
3064 :
3065 4 : {
3066 4 : pretty_printer pp;
3067 4 : abc.hexdump_to_pp (&pp, hexdump_options ());
3068 4 : ASSERT_STREQ
3069 : (pp_formatted_text (&pp),
3070 : ("+------------+--------+---+\n"
3071 : "|[bytes 0..3)|61 62 63|abc|\n"
3072 : "+------------+--------+---+\n"));
3073 4 : }
3074 :
3075 : /* Verify accessing chars within a RAW_DATA_CST. */
3076 4 : {
3077 4 : auto &a = abc.get_byte_at_offset (0_bytes);
3078 4 : ASSERT_SAME_SYMBOLIC_NODE (a, mgr.get_uint8 ('a'));
3079 :
3080 4 : auto &b = abc.get_byte_at_offset (1_byte);
3081 4 : ASSERT_SAME_SYMBOLIC_NODE (b, mgr.get_uint8 ('b'));
3082 :
3083 4 : auto &c = abc.get_byte_at_offset (2_bytes);
3084 4 : ASSERT_SAME_SYMBOLIC_NODE (c, mgr.get_uint8 ('c'));
3085 : }
3086 4 : }
3087 :
3088 : /* Test of a raw data cst with multiple embedded zero bytes. */
3089 :
3090 : static void
3091 4 : test_raw_data_constant_2 ()
3092 : {
3093 4 : tree raw_data_cst_ptr = make_raw_data_constant ("a\0b\0c\0", 6);
3094 :
3095 4 : symbolic::node_manager node_mgr;
3096 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3097 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3098 :
3099 4 : auto &a0b0c0 = mgr.get_bits_for_constant (raw_data_cst_ptr);
3100 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_size (),
3101 : bit_mgr.get_concrete (bits_from_bytes (6_bytes)));
3102 4 : a0b0c0.to_json ();
3103 :
3104 4 : {
3105 4 : pretty_printer pp;
3106 4 : a0b0c0.hexdump_to_pp (&pp, hexdump_options ());
3107 4 : ASSERT_STREQ
3108 : (pp_formatted_text (&pp),
3109 : ("+------------+-----------+----+\n"
3110 : "|[bytes 0..4)|61 00 62 00|a.b.|\n"
3111 : "+------------+-----------+----+\n"
3112 : "|[bytes 4..6)|63 00 |c. |\n"
3113 : "+------------+-----------+----+\n"));
3114 4 : }
3115 :
3116 : /* Verify accessing chars within a RAW_DATA_CST. */
3117 4 : {
3118 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (0_bytes),
3119 : mgr.get_uint8 ('a'));
3120 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (1_byte),
3121 : mgr.get_uint8 (0));
3122 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (2_bytes),
3123 : mgr.get_uint8 ('b'));
3124 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (3_bytes),
3125 : mgr.get_uint8 (0));
3126 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (4_bytes),
3127 : mgr.get_uint8 ('c'));
3128 4 : ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (5_bytes),
3129 : mgr.get_uint8 (0));
3130 : }
3131 :
3132 : /* String scans should locate the NUL bytes. */
3133 4 : {
3134 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (0_bytes),
3135 : string_scan::found_nul (1_byte));
3136 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (1_byte),
3137 : string_scan::found_nul (1_byte));
3138 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (2_bytes),
3139 : string_scan::found_nul (3_bytes));
3140 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (3_bytes),
3141 : string_scan::found_nul (3_bytes));
3142 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (4_bytes),
3143 : string_scan::found_nul (5_bytes));
3144 4 : ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (5_bytes),
3145 : string_scan::found_nul (5_bytes));
3146 : }
3147 4 : }
3148 :
3149 : /* Test of an empty raw data cst. */
3150 :
3151 : static void
3152 4 : test_raw_data_constant_empty ()
3153 : {
3154 4 : tree raw_data_cst_ptr = make_raw_data_constant ("", 0);
3155 :
3156 4 : symbolic::node_manager node_mgr;
3157 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3158 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3159 :
3160 4 : auto &bv = mgr.get_bits_for_constant (raw_data_cst_ptr);
3161 4 : ASSERT_SAME_SYMBOLIC_NODE (bv.get_size (),
3162 : bit_mgr.get_concrete (bits_from_bytes (0_bytes)));
3163 4 : ASSERT_SAME_SYMBOLIC_NODE (bv,
3164 : node_mgr.get_bit_vector_manager ().get_empty ());
3165 4 : }
3166 :
3167 : static void
3168 4 : test_concat ()
3169 : {
3170 4 : symbolic::node_manager node_mgr;
3171 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3172 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3173 :
3174 4 : auto &char_a
3175 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'a'));
3176 4 : auto &char_b
3177 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'b'));
3178 4 : auto &char_x
3179 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'x'));
3180 4 : auto &char_y
3181 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'y'));
3182 :
3183 4 : auto &ab = mgr.get_concat_bits ({&char_a, &char_b});
3184 4 : ASSERT_SAME_SYMBOLIC_NODE (ab.get_size (),
3185 : bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
3186 4 : ab.to_json ();
3187 :
3188 4 : auto &xy
3189 4 : = mgr.get_concat_bits ({&char_x, &char_y});
3190 4 : ASSERT_SAME_SYMBOLIC_NODE (xy.get_size (),
3191 : bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
3192 16 : for (concrete_byte_offset i = 0_bytes; i < 2_bytes; ++i)
3193 8 : ASSERT_EQ (xy.scan_for_first_zero_byte (i),
3194 4 : string_scan::beyond_domain (2_bytes));
3195 :
3196 4 : auto &single_element
3197 4 : = mgr.get_concat_bits ({&char_a});
3198 4 : ASSERT_SAME_SYMBOLIC_NODE (single_element, char_a);
3199 :
3200 : /* Verity concat (empty, empty) --> empty. */
3201 4 : ASSERT_SAME_SYMBOLIC_NODE
3202 : (mgr.get_concat_bits ({&mgr.get_empty (), &mgr.get_empty ()}),
3203 : mgr.get_empty ());
3204 :
3205 : /* Verity concat (a, empty) --> a. */
3206 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concat_bits ({&char_a, &mgr.get_empty ()}),
3207 : char_a);
3208 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concat_bits ({&mgr.get_empty (), &char_a}),
3209 : char_a);
3210 :
3211 : /* Verify concat(a, a) --> a * 2. */
3212 4 : auto &aa
3213 4 : = mgr.get_concat_bits ({&char_a, &char_a});
3214 4 : ASSERT_SAME_SYMBOLIC_NODE (aa.get_size (),
3215 : bit_mgr.get_concrete (16_bits));
3216 4 : ASSERT_SAME_SYMBOLIC_NODE
3217 : (aa,
3218 : mgr.get_repeated_bits (char_a, 2));
3219 :
3220 : /* Verify concat(a, a, a) --> a * 3. */
3221 4 : auto &aaa
3222 : = mgr.get_concat_bits
3223 4 : ({&char_a, &char_a, &char_a});
3224 4 : ASSERT_SAME_SYMBOLIC_NODE (aaa.get_size (),
3225 : bit_mgr.get_concrete (24_bits));
3226 4 : ASSERT_SAME_SYMBOLIC_NODE
3227 : (aaa,
3228 : mgr.get_repeated_bits (char_a, 3));
3229 :
3230 : /* Verify concat(a * 2, a) --> a * 3. */
3231 4 : {
3232 4 : auto &bits = mgr.get_concat_bits ({&aa, &char_a});
3233 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, aaa);
3234 : }
3235 :
3236 : /* Verify concat(a, a * 2) --> a * 3. */
3237 4 : {
3238 4 : auto &bits = mgr.get_concat_bits ({&char_a, &aa});
3239 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, aaa);
3240 : }
3241 :
3242 : /* Verify concat(a * 2, a * 2) --> a * 4. */
3243 4 : {
3244 4 : auto &bits = mgr.get_concat_bits ({&aa, &aa});
3245 4 : ASSERT_SAME_SYMBOLIC_NODE
3246 : (bits,
3247 : mgr.get_repeated_bits (char_a, 4));
3248 : }
3249 :
3250 : /* Verify concat(a * 2, a, a * 2) --> a * 5. */
3251 4 : {
3252 4 : auto &bits = mgr.get_concat_bits ({&aa, &char_a, &aa});
3253 4 : ASSERT_SAME_SYMBOLIC_NODE
3254 : (bits,
3255 : mgr.get_repeated_bits (char_a, 5));
3256 : }
3257 :
3258 : /* Verify concat(a, a, b, b) --> concat(a * 2, b * 2). */
3259 4 : {
3260 4 : auto &bits
3261 : = mgr.get_concat_bits
3262 4 : ({&char_a, &char_a, &char_b, &char_b});
3263 4 : ASSERT_SAME_SYMBOLIC_NODE
3264 : (bits,
3265 : mgr.get_concat_bits
3266 : ({&mgr.get_repeated_bits (char_a, 2),
3267 : &mgr.get_repeated_bits (char_b, 2)}));
3268 : }
3269 :
3270 : /* Verify concat of poisoneds. */
3271 4 : {
3272 : /* Verify concat(poisoned(m), poisoned(n) --> poisoned(m + n)
3273 : for same kind of poison. */
3274 4 : {
3275 4 : auto &bits = mgr.get_concat_bits
3276 8 : ({&mgr.get_poisoned_bits (2_bits, poison_kind::uninit),
3277 8 : &mgr.get_poisoned_bits (3_bits, poison_kind::uninit)});
3278 4 : ASSERT_SAME_SYMBOLIC_NODE
3279 : (bits,
3280 : mgr.get_poisoned_bits (5_bits, poison_kind::uninit));
3281 : }
3282 :
3283 : // Verify that we don't fold the concat of non-equal kinds of poison
3284 4 : {
3285 4 : auto &bits = mgr.get_concat_bits
3286 8 : ({&mgr.get_poisoned_bits (2_bits, poison_kind::uninit),
3287 8 : &mgr.get_poisoned_bits (3_bits, poison_kind::freed)});
3288 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3289 : (bits,
3290 : ("concat_bit_vector[size: 5 bits]\n"
3291 : "+- poisoned_bit_vector[size: 2 bits]: uninit\n"
3292 : "`- poisoned_bit_vector[size: 3 bits]: freed\n"));
3293 : }
3294 : }
3295 :
3296 : /* Verify concat of tristates. */
3297 4 : {
3298 : /* Verify concat(tristate(m), tristate(n) --> tristate(m + n)
3299 : for same tristate. */
3300 4 : {
3301 4 : auto &bits
3302 8 : = mgr.get_concat_bits ({&mgr.get_all_zeros (2_bits),
3303 8 : &mgr.get_all_zeros (3_bits)});
3304 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, mgr.get_all_zeros (5_bits));
3305 : }
3306 :
3307 : // Verify that we don't fold the concat of non-equal tristates
3308 4 : {
3309 4 : auto &bits
3310 : = mgr.get_concat_bits
3311 4 : ({
3312 4 : &mgr.get_all_zeros (2_bits),
3313 8 : &mgr.get_all_ones (3_bits)
3314 : });
3315 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3316 : (bits,
3317 : ("concat_bit_vector[size: 5 bits]\n"
3318 : "+- tristate_bit_vector[size: 2 bits]: false bits\n"
3319 : "`- tristate_bit_vector[size: 3 bits]: true bits\n"));
3320 4 : ASSERT_EQ (bits.get_tristate_at_offset (0_bits), tristate (false));
3321 4 : ASSERT_EQ (bits.get_tristate_at_offset (1_bit), tristate (false));
3322 4 : ASSERT_EQ (bits.get_tristate_at_offset (2_bits), tristate (true));
3323 4 : ASSERT_EQ (bits.get_tristate_at_offset (3_bits), tristate (true));
3324 4 : ASSERT_EQ (bits.get_tristate_at_offset (4_bits), tristate (true));
3325 :
3326 4 : {
3327 4 : pretty_printer pp;
3328 4 : hexdump_options hexdump_opts;
3329 4 : hexdump_opts.m_show_binary = true;
3330 4 : hexdump_opts.m_show_hex = false;
3331 4 : hexdump_opts.m_show_ascii = false;
3332 4 : bits.hexdump_to_pp (&pp, hexdump_opts);
3333 4 : ASSERT_STREQ
3334 : (pp_formatted_text (&pp),
3335 : "+-----------+-----+\n"
3336 : "|[bits 0..5)|00111|\n"
3337 : "+-----------+-----+\n");
3338 4 : }
3339 : }
3340 : }
3341 :
3342 : /* Verify concat of concat --> concat. */
3343 : /*
3344 : e.g.
3345 : concat(concat(A, B), concat(X, Y)) --> concat(A, B, X, Y);
3346 : */
3347 4 : auto &abxy
3348 4 : = mgr.get_concat_bits ({&ab, &xy});
3349 4 : ASSERT_SAME_SYMBOLIC_NODE (abxy.get_size (),
3350 : bit_mgr.get_concrete (32_bits));
3351 4 : ASSERT_SAME_SYMBOLIC_NODE
3352 : (abxy,
3353 : mgr.get_concat_bits ({&char_a, &char_b, &char_x, &char_y}));
3354 4 : abxy.to_json ();
3355 24 : for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
3356 16 : ASSERT_EQ (abxy.scan_for_first_zero_byte (i),
3357 4 : string_scan::beyond_domain (4_bytes));
3358 :
3359 : /* Verify concat of concat.
3360 : This doesn't repeat right now; it instead unwraps everything. */
3361 4 : auto &abab
3362 4 : = mgr.get_concat_bits ({&ab, &ab});
3363 4 : ASSERT_SAME_SYMBOLIC_NODE (abab.get_size (),
3364 : bit_mgr.get_concrete (32_bits));
3365 4 : ASSERT_SAME_SYMBOLIC_NODE
3366 : (abab,
3367 : mgr.get_concat_bits ({&char_a, &char_b, &char_a, &char_b}));
3368 24 : for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
3369 16 : ASSERT_EQ (abab.scan_for_first_zero_byte (i),
3370 4 : string_scan::beyond_domain (4_bytes));
3371 4 : }
3372 :
3373 : static void
3374 4 : test_cropped ()
3375 : {
3376 4 : symbolic::node_manager node_mgr;
3377 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
3378 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3379 :
3380 4 : auto &a = bv_mgr.get_named_test_bit_vector (10_bytes, "A");
3381 4 : auto &b = bv_mgr.get_named_test_bit_vector (10_bytes, "B");
3382 :
3383 4 : a.to_json ();
3384 :
3385 : /* Verify the "can't fold" case, and dumping. */
3386 4 : {
3387 12 : auto &bits = a.get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes));
3388 4 : ASSERT_SAME_SYMBOLIC_NODE (bits.get_size (),
3389 : bit_mgr.get_concrete (16_bits));
3390 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3391 : (bits,
3392 : ("cropped_bit_vector[size: 2 bytes]: [bytes 5..7)\n"
3393 : "`- uncropped: named_test_bit_vector[size: 10 bytes]: 'A'\n"));
3394 4 : bits.to_json ();
3395 16 : for (concrete_byte_offset i = 0_bytes; i < 2_bytes; ++i)
3396 8 : ASSERT_EQ (bits.scan_for_first_zero_byte (i),
3397 4 : string_scan::cannot_scan (i));
3398 20 : for (concrete_byte_offset i = 2_bytes; i < 5_bytes; ++i)
3399 12 : ASSERT_EQ (bits.scan_for_first_zero_byte (i),
3400 4 : string_scan::beyond_domain (i));
3401 :
3402 : // Verify that consolidation works
3403 12 : ASSERT_SAME_SYMBOLIC_NODE
3404 : (a.get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)),
3405 : bits);
3406 :
3407 : // Verify that we don't erroneously consolidate...
3408 : // ...different inner bit_vector:
3409 12 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3410 : (b.get_cropped_bytes (concrete_byte_range (2_bytes, 2_bytes)),
3411 : bits);
3412 : // ...different start offset:
3413 12 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3414 : (a.get_cropped_bytes (concrete_byte_range (6_bytes, 2_bytes)),
3415 : bits);
3416 : // ...different size:
3417 12 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3418 : (a.get_cropped_bytes (concrete_byte_range (5_bytes, 1_byte)),
3419 : bits);
3420 : }
3421 :
3422 : /* Verify that A[0..size(A)] --> A. */
3423 4 : {
3424 12 : auto &bits = a.get_cropped_bytes (concrete_byte_range (0_bytes, 10_bytes));
3425 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, a);
3426 : }
3427 :
3428 : /* Verify that A[(empty)] --> empty. */
3429 4 : {
3430 12 : auto &bits = a.get_cropped_bytes (concrete_byte_range (0_bytes, 0_bytes));
3431 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, bv_mgr.get_empty ());
3432 : }
3433 :
3434 : /* Verify that concat(A[p, q], A[q, r]) --> A[p, r]. */
3435 4 : {
3436 12 : auto &a35 = a.get_cropped_bytes (concrete_byte_range (3_bytes, 3_bytes));
3437 4 : ASSERT_SAME_SYMBOLIC_NODE
3438 : (a35.get_size (),
3439 : bit_mgr.get_concrete (bits_from_bytes (3_bytes)));
3440 12 : auto &a67 = a.get_cropped_bytes (concrete_byte_range (6_bytes, 2_bytes));
3441 4 : ASSERT_SAME_SYMBOLIC_NODE
3442 : (a67.get_size (),
3443 : bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
3444 4 : auto &a35a67 = bv_mgr.get_concat_bits ({&a35, &a67});
3445 4 : ASSERT_SAME_SYMBOLIC_NODE
3446 : (a35a67.get_size (),
3447 : bit_mgr.get_concrete (bits_from_bytes (5_bytes)));
3448 12 : ASSERT_SAME_SYMBOLIC_NODE
3449 : (a35a67,
3450 : a.get_cropped_bytes (concrete_byte_range (3_bytes, 5_bytes)));
3451 : }
3452 :
3453 : /* Verify that concat(A[0, n], A[n, size(A)]) --> A. */
3454 4 : {
3455 12 : auto &a06 = a.get_cropped_bytes (concrete_byte_range (0_bytes, 7_bytes));
3456 12 : auto &a79 = a.get_cropped_bytes (concrete_byte_range (7_bytes, 3_bytes));
3457 4 : auto &a06a79 = bv_mgr.get_concat_bits ({&a06, &a79});
3458 4 : ASSERT_SAME_SYMBOLIC_NODE (a06a79, a);
3459 : }
3460 :
3461 : /* Verify crop of crop: e.g. A[5..10][2..3] --> A[7..8]. */
3462 4 : {
3463 12 : auto &a59 = a.get_cropped_bytes (concrete_byte_range (5_bytes, 5_bytes));
3464 4 : auto &a59_23
3465 12 : = a59.get_cropped_bytes (concrete_byte_range (2_bytes, 2_bytes));
3466 12 : ASSERT_SAME_SYMBOLIC_NODE
3467 : (a59_23,
3468 : a.get_cropped_bytes (concrete_byte_range (7_bytes, 2_bytes)));
3469 : }
3470 :
3471 : // Verify poisoned(x)[m..n] --> poisoned(x, sizeof(m..n)).
3472 4 : {
3473 4 : auto &bits
3474 8 : = (bv_mgr.get_poisoned_bits (bits_from_bytes (10_bytes),
3475 : poison_kind::uninit)
3476 12 : .get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)));
3477 4 : ASSERT_SAME_SYMBOLIC_NODE
3478 : (bits.get_size (),
3479 : bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
3480 4 : ASSERT_SAME_SYMBOLIC_NODE
3481 : (bits,
3482 : bv_mgr.get_poisoned_bits (16_bits, poison_kind::uninit));
3483 : }
3484 :
3485 : // Verify tristate(x)[m..n] --> tristate(x, sizeof(m..n)).
3486 4 : {
3487 4 : auto &bits
3488 4 : = (bv_mgr.get_all_zeros (10_bytes)
3489 12 : .get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)));
3490 4 : ASSERT_SAME_SYMBOLIC_NODE
3491 : (bits.get_size (),
3492 : bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
3493 4 : ASSERT_SAME_SYMBOLIC_NODE (bits, bv_mgr.get_all_zeros (16_bits));
3494 : }
3495 :
3496 : /* crop of concat e.g.:
3497 : concat(X1, ... Xn)[a, b] --> concat(X1[...], ..., Xn[...])
3498 : */
3499 4 : {
3500 4 : auto &x = bv_mgr.get_named_test_bit_vector (1_byte, "X");
3501 4 : auto &y = bv_mgr.get_named_test_bit_vector (1_byte, "Y");
3502 4 : auto &z = bv_mgr.get_named_test_bit_vector (1_byte, "Z");
3503 4 : auto &xyz = bv_mgr.get_concat_bits ({&x, &y, &z});
3504 12 : ASSERT_SAME_SYMBOLIC_NODE
3505 : (xyz.get_cropped_bytes (concrete_byte_range (0_bytes, 1_byte)),
3506 : x);
3507 12 : ASSERT_SAME_SYMBOLIC_NODE
3508 : (xyz.get_cropped_bytes (concrete_byte_range (1_byte, 1_byte)),
3509 : y);
3510 12 : ASSERT_SAME_SYMBOLIC_NODE
3511 : (xyz.get_cropped_bytes (concrete_byte_range (2_bytes, 1_byte)),
3512 : z);
3513 12 : ASSERT_SAME_SYMBOLIC_NODE
3514 : (xyz.get_cropped_bytes (concrete_byte_range (0_bytes, 2_bytes)),
3515 : bv_mgr.get_concat_bits ({&x, &y}));
3516 12 : ASSERT_SAME_SYMBOLIC_NODE
3517 : (xyz.get_cropped_bits (concrete_bit_range (3_bits, 9_bits)),
3518 : bv_mgr.get_concat_bits
3519 : ({&x.get_suffix (5_bits), &y.get_prefix (4_bits)}));
3520 : }
3521 :
3522 4 : {
3523 : /* 20 bytes: 5 repeats of a 4 byte vector:
3524 : If x is [abcd] then we have bytes 0-19:
3525 : . 1111111111
3526 : . 01234567890123456789
3527 : . abcdabcdabcdabcdabcd */
3528 4 : auto &x = bv_mgr.get_named_test_bit_vector (4_bytes, "X");
3529 4 : auto &x_times_5 = bv_mgr.get_repeated_bits (x, 5);
3530 12 : ASSERT_SAME_SYMBOLIC_NODE
3531 : (x_times_5.get_cropped_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3532 : x_times_5);
3533 :
3534 : /* Getting individual bytes. */
3535 88 : for (concrete_byte_offset i = 0_bytes; i < 20_bytes; ++i)
3536 80 : ASSERT_SAME_SYMBOLIC_NODE
3537 : (x_times_5.get_byte_at_offset (i),
3538 4 : x.get_byte_at_offset (i.floor_mod (4_bytes)));
3539 :
3540 : // Cropping on an exact boundary should give us X again:
3541 12 : ASSERT_SAME_SYMBOLIC_NODE
3542 : (x_times_5.get_cropped_bytes (concrete_byte_range (0_bytes, 4_bytes)),
3543 : x);
3544 12 : ASSERT_SAME_SYMBOLIC_NODE
3545 : (x_times_5.get_cropped_bytes (concrete_byte_range (4_bytes, 4_bytes)),
3546 : x);
3547 :
3548 : /* Cropping at awkward boundaries. */
3549 : /* Bytes [3,5). */
3550 12 : ASSERT_SAME_SYMBOLIC_NODE
3551 : (x_times_5.get_cropped_bytes (concrete_byte_range (3_bytes, 2_bytes)),
3552 : bv_mgr.get_concat_bits
3553 : ({&x.get_suffix (1_byte),
3554 : &x.get_prefix (1_byte)}));
3555 :
3556 : /* Bytes [3,19):
3557 : . 1111111111
3558 : . 01234567890123456789
3559 : . abcdabcdabcdabcdabcd
3560 : . [PQQQQQQQQQQQQRRR]
3561 : should give us:
3562 : - P: the last byte of X
3563 : - Q: 3 repeats of X
3564 : - R: the first 3 bytes of X. */
3565 28 : ASSERT_SAME_SYMBOLIC_NODE
3566 : (x_times_5.get_cropped_bytes (concrete_byte_range (3_bytes, 16_bytes)),
3567 : bv_mgr.get_concat_bits
3568 : ({&x.get_cropped_bytes (concrete_byte_range (3_bytes, 1_byte)),
3569 : &bv_mgr.get_repeated_bits (x, 3),
3570 : &x.get_cropped_bytes (concrete_byte_range (0_bytes, 3_bytes))}));
3571 : }
3572 4 : }
3573 :
3574 : static void
3575 4 : test_named_test_bit_vector ()
3576 : {
3577 4 : symbolic::node_manager node_mgr;
3578 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
3579 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3580 :
3581 4 : auto &x = bv_mgr.get_named_test_bit_vector (1024_bytes, "X");
3582 4 : ASSERT_SAME_SYMBOLIC_NODE
3583 : (x.get_size (),
3584 : bit_mgr.get_concrete (bits_from_bytes (1024_bytes)));
3585 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3586 : (x,
3587 : "named_test_bit_vector[size: 1024 bytes]: 'X'\n");
3588 4 : x.to_json ();
3589 4 : }
3590 :
3591 : static void
3592 4 : test_poisoned ()
3593 : {
3594 4 : symbolic::node_manager node_mgr;
3595 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3596 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
3597 :
3598 4 : auto &uninit_bit = mgr.get_poisoned_bits (1_bit, poison_kind::uninit);
3599 :
3600 4 : ASSERT_SAME_SYMBOLIC_NODE (uninit_bit.get_size (),
3601 : bit_mgr.get_concrete (1_bit));
3602 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (uninit_bit,
3603 : "poisoned_bit_vector[size: 1 bit]: uninit\n");
3604 :
3605 4 : ASSERT_SAME_SYMBOLIC_NODE
3606 : (mgr.get_poisoned_bits (0_bits, poison_kind::uninit),
3607 : mgr.get_empty ());
3608 :
3609 4 : uninit_bit.to_json ();
3610 :
3611 4 : auto &freed_bit = mgr.get_poisoned_bits (1_bit, poison_kind::freed);
3612 4 : ASSERT_SAME_SYMBOLIC_NODE (freed_bit.get_size (),
3613 : bit_mgr.get_concrete (1_bit));
3614 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (freed_bit,
3615 : "poisoned_bit_vector[size: 1 bit]: freed\n");
3616 :
3617 4 : freed_bit.to_json ();
3618 :
3619 4 : auto &three_uninit_bits
3620 4 : = mgr.get_poisoned_bits (3_bits, poison_kind::uninit);
3621 4 : ASSERT_SAME_SYMBOLIC_NODE (three_uninit_bits.get_size (),
3622 : bit_mgr.get_concrete (3_bits));
3623 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (three_uninit_bits,
3624 : "poisoned_bit_vector[size: 3 bits]: uninit\n");
3625 4 : }
3626 :
3627 : static void
3628 4 : test_repeated ()
3629 : {
3630 4 : symbolic::node_manager node_mgr;
3631 4 : auto &mgr = node_mgr.get_bit_vector_manager ();
3632 :
3633 4 : auto &byte_00 = mgr.get_all_zeros (1_byte);
3634 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3635 : (byte_00,
3636 : "tristate_bit_vector[size: 1 byte]: false bits\n");
3637 :
3638 : /* Verify that repeats of tristate_bit_vector are folded to
3639 : tristate_bit_vector. */
3640 4 : auto &kilobyte_of_zeros = mgr.get_repeated_bits (byte_00, 1024);
3641 4 : ASSERT_SAME_SYMBOLIC_NODE (kilobyte_of_zeros, mgr.get_all_zeros (1024_bytes));
3642 :
3643 4 : kilobyte_of_zeros.to_json ();
3644 :
3645 : // Verify that 0 repeats is the empty bit vector:
3646 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_repeated_bits (byte_00, 0),
3647 : mgr.get_empty ());
3648 :
3649 : // Verify that we fold repeats of repeats into repeats:
3650 4 : auto &char_A
3651 4 : = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'A'));
3652 4 : auto &ten_As = mgr.get_repeated_bits (char_A, 10);
3653 4 : auto &two_times_ten_As = mgr.get_repeated_bits (ten_As, 2);
3654 4 : ASSERT_SAME_SYMBOLIC_NODE
3655 : (two_times_ten_As,
3656 : mgr.get_repeated_bits (char_A, 20));
3657 :
3658 4 : {
3659 4 : pretty_printer pp;
3660 4 : hexdump_options hexdump_opts;
3661 4 : hexdump_opts.m_bytes_per_line = 10_bytes;
3662 4 : two_times_ten_As.hexdump_to_pp (&pp, hexdump_opts);
3663 4 : ASSERT_STREQ
3664 : (pp_formatted_text (&pp),
3665 : "+--------------+-----------------------------+----------+\n"
3666 : "| [bytes 0..10)|41 41 41 41 41 41 41 41 41 41|AAAAAAAAAA|\n"
3667 : "+--------------+-----------------------------+----------+\n"
3668 : "|[bytes 10..20)|41 41 41 41 41 41 41 41 41 41|AAAAAAAAAA|\n"
3669 : "+--------------+-----------------------------+----------+\n");
3670 4 : }
3671 4 : {
3672 4 : pretty_printer pp;
3673 4 : hexdump_options hexdump_opts;
3674 4 : hexdump_opts.m_show_binary = true;
3675 4 : two_times_ten_As.hexdump_to_pp (&pp, hexdump_opts);
3676 4 : ASSERT_STREQ
3677 : (pp_formatted_text (&pp),
3678 : ("+--------------+-----------------------------------+-----------+----+\n"
3679 : "| [bytes 0..4)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
3680 : "+--------------+-----------------------------------+-----------+----+\n"
3681 : "| [bytes 4..8)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
3682 : "+--------------+-----------------------------------+-----------+----+\n"
3683 : "| [bytes 8..12)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
3684 : "+--------------+-----------------------------------+-----------+----+\n"
3685 : "|[bytes 12..16)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
3686 : "+--------------+-----------------------------------+-----------+----+\n"
3687 : "|[bytes 16..20)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
3688 : "+--------------+-----------------------------------+-----------+----+\n"));
3689 4 : }
3690 :
3691 : // Verify that repeat(A, 1) --> A.
3692 4 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_repeated_bits (char_A, 1), char_A);
3693 4 : }
3694 :
3695 : static void
3696 4 : test_bit_vector_from_svalue ()
3697 : {
3698 4 : symbolic::node_manager node_mgr;
3699 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
3700 4 : auto &rmm = node_mgr.get_svalue_manager ();
3701 :
3702 4 : auto *unknown_char_sval
3703 4 : = rmm.get_or_create_unknown_svalue (unsigned_char_type_node);
3704 4 : ASSERT_SAME_SYMBOLIC_NODE
3705 : (bv_mgr.get_bit_vector_from_svalue (*unknown_char_sval),
3706 : bv_mgr.get_unknown_bits (8_bits));
3707 :
3708 4 : unknown_char_sval->to_json ();
3709 :
3710 : /* Verify that we remove redundant casts
3711 : e.g. BIT_VECTOR_FOR (UNARY_OP(signed, NOP_EXPR, SVAL(unsigned)))
3712 : folds to BIT_VECTOR_FOR (SVAL(unsigned)). */
3713 4 : {
3714 4 : placeholder_svalue sval (node_mgr.alloc_node_id (),
3715 4 : integer_type_node, "x");
3716 4 : auto *cast_sval = rmm.get_or_create_cast (unsigned_type_node, &sval);
3717 4 : ASSERT_DIFFERENT_SYMBOLIC_NODE (sval, *cast_sval);
3718 4 : ASSERT_SAME_SYMBOLIC_NODE (bv_mgr.get_bit_vector_from_svalue (sval),
3719 : bv_mgr.get_bit_vector_from_svalue (*cast_sval));
3720 4 : }
3721 :
3722 : /* Make a bit_vector from bitwise "and" and "or" against a concrete mask to
3723 : verify what we "know" about individual bits and bytes (using the
3724 : irange_bitmask). */
3725 4 : {
3726 4 : placeholder_svalue y (node_mgr.alloc_node_id (),
3727 4 : uint32_type_node, "y");
3728 4 : auto *mask = rmm.get_or_create_int_cst (uint32_type_node, 0xff00ff00);
3729 :
3730 4 : hexdump_options hexdump_opts;
3731 4 : hexdump_opts.m_show_binary = true;
3732 4 : hexdump_opts.m_show_ascii = false;
3733 :
3734 4 : {
3735 4 : auto *bitwise_and = rmm.get_or_create_binop (uint32_type_node,
3736 : BIT_AND_EXPR,
3737 : &y,
3738 : mask);
3739 4 : auto &bv = bv_mgr.get_bit_vector_from_svalue (*bitwise_and);
3740 :
3741 : // Check what we know about individual bits in the bit_vector
3742 40 : for (auto i = 0_bits; i < 8_bits; ++i)
3743 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (false));
3744 40 : for (auto i = 8_bits; i < 16_bits; ++i)
3745 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
3746 40 : for (auto i = 16_bits; i < 24_bits; ++i)
3747 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (false));
3748 40 : for (auto i = 24_bits; i < 32_bits; ++i)
3749 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
3750 :
3751 : // Check what we know about individual bytes in the bit_vector
3752 4 : ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (0_bytes),
3753 : bv_mgr.get_uint8 (0));
3754 4 : ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (2_bytes),
3755 : bv_mgr.get_uint8 (0));
3756 :
3757 4 : pretty_printer pp;
3758 4 : bv.hexdump_to_pp (&pp, hexdump_opts);
3759 4 : ASSERT_STREQ
3760 : (pp_formatted_text (&pp),
3761 : "+------------+-----------------------------------+-----------+\n"
3762 : "|[bytes 0..4)|00000000 ???????? 00000000 ????????|00 ?? 00 ??|\n"
3763 : "+------------+-----------------------------------+-----------+\n");
3764 4 : }
3765 4 : {
3766 4 : auto *bitwise_or = rmm.get_or_create_binop (uint32_type_node,
3767 : BIT_IOR_EXPR,
3768 : &y,
3769 : mask);
3770 4 : auto &bv = bv_mgr.get_bit_vector_from_svalue (*bitwise_or);
3771 :
3772 : // Check what we know about individual bits in the bit_vector
3773 40 : for (auto i = 0_bits; i < 8_bits; ++i)
3774 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
3775 40 : for (auto i = 8_bits; i < 16_bits; ++i)
3776 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (true));
3777 40 : for (auto i = 16_bits; i < 24_bits; ++i)
3778 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
3779 40 : for (auto i = 24_bits; i < 32_bits; ++i)
3780 32 : ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (true));
3781 :
3782 : // Check what we know about individual bytes in the bit_vector
3783 4 : ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (1_byte),
3784 : bv_mgr.get_uint8 (0xff));
3785 4 : ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (3_bytes),
3786 : bv_mgr.get_uint8 (0xff));
3787 :
3788 4 : pretty_printer pp;
3789 4 : bv.hexdump_to_pp (&pp, hexdump_opts);
3790 4 : ASSERT_STREQ
3791 : (pp_formatted_text (&pp),
3792 : "+------------+-----------------------------------+-----------+\n"
3793 : "|[bytes 0..4)|???????? 11111111 ???????? 11111111|?? ff ?? ff|\n"
3794 : "+------------+-----------------------------------+-----------+\n");
3795 4 : }
3796 4 : }
3797 4 : }
3798 :
3799 : /* Consider this buggy C code (writing to a fixed-size buffer with no
3800 : size checks on inputs):
3801 : | char buf[1024];
3802 : | len_a = strlen (str_a);
3803 : | len_b = strlen (str_b);
3804 : | memcpy (buf, str_a, len_a);
3805 : | memcpy (buf + len_a, str_b, len_b);
3806 : | buf[len_a + len_b] = '\0';
3807 : */
3808 : static void
3809 4 : test_example_strcat ()
3810 : {
3811 4 : symbolic::node_manager node_mgr;
3812 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
3813 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
3814 :
3815 4 : auto &strlen_a = byte_mgr.get_named_test_scalar ("strlen(a)");
3816 4 : auto &strlen_b = byte_mgr.get_named_test_scalar ("strlen(b)");
3817 4 : auto &a = bv_mgr.get_named_test_bit_vector (strlen_a + 1_byte, "a");
3818 4 : auto &b = bv_mgr.get_named_test_bit_vector (strlen_b + 1_byte, "b");
3819 :
3820 4 : auto &bv_for_buf = bv_mgr.get_concat_bits
3821 12 : ({&a.get_prefix (strlen_a),
3822 4 : &b.get_prefix (strlen_b),
3823 4 : &bv_mgr.get_uint8 (0)});
3824 :
3825 4 : ASSERT_SAME_SYMBOLIC_NODE
3826 : (bv_for_buf.get_size (),
3827 : bits_from_bytes (strlen_a + strlen_b + 1_byte));
3828 4 : ASSERT_SAME_SYMBOLIC_NODE
3829 : (*maybe_bytes_from_bits (bv_for_buf.get_size ()),
3830 : strlen_a + strlen_b + 1_byte);
3831 4 : }
3832 :
3833 : static void
3834 4 : test_from_unfoldable_bit_contents ()
3835 : {
3836 4 : symbolic::node_manager mgr;
3837 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3838 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3839 :
3840 4 : auto &ubc_a = bc_mgr.get_named_test_bit_contents ("A");
3841 4 : auto &ubc_b = bc_mgr.get_named_test_bit_contents ("B");
3842 :
3843 12 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
3844 : (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3845 : ("bit_vector_from_ubc[size: 10 bytes]\n"
3846 : "+- bit_contents: named_test_bit_contents: A\n"
3847 : "`- range: symbolic range\n"
3848 : " +- start offset: concrete_scalar<bits>: 0\n"
3849 : " `- size: concrete_scalar<bits>: 80\n"));
3850 :
3851 20 : ASSERT_SAME_SYMBOLIC_NODE
3852 : (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3853 : ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
3854 :
3855 20 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3856 : (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3857 : ubc_a.get_bytes (concrete_byte_range (0_bytes, 9_bytes)));
3858 :
3859 20 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3860 : (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3861 : ubc_b.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
3862 :
3863 : /* Concat of touching ranges from same bit contents should
3864 : be folded to a single range from that bit contents. */
3865 28 : ASSERT_SAME_SYMBOLIC_NODE
3866 : (bv_mgr.get_concat_bits
3867 : ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
3868 : &ubc_a.get_bytes (concrete_byte_range (4_bytes, 6_bytes))}),
3869 : ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
3870 : /* ...but not for those that don't touch: */
3871 28 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3872 : (bv_mgr.get_concat_bits
3873 : ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
3874 : &ubc_a.get_bytes (concrete_byte_range (5_bytes, 5_bytes))}),
3875 : ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
3876 : /* ...but not for those from different bit contents: */
3877 28 : ASSERT_DIFFERENT_SYMBOLIC_NODE
3878 : (bv_mgr.get_concat_bits
3879 : ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
3880 : &ubc_b.get_bytes (concrete_byte_range (4_bytes, 6_bytes))}),
3881 : ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
3882 :
3883 : /* Cropping a range from a ubc should give the appropriate
3884 : subrange from the ubc. */
3885 4 : auto &a_bytes_10_14
3886 12 : = ubc_a.get_bytes (concrete_byte_range (10_bytes, 5_bytes));
3887 12 : ASSERT_SAME_SYMBOLIC_NODE
3888 : (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (0_bytes, 5_bytes)),
3889 : a_bytes_10_14);
3890 20 : ASSERT_SAME_SYMBOLIC_NODE
3891 : (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (0_bytes, 1_byte)),
3892 : ubc_a.get_bytes (concrete_byte_range (10_bytes, 1_byte)));
3893 20 : ASSERT_SAME_SYMBOLIC_NODE
3894 : (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (4_bytes, 1_byte)),
3895 : ubc_a.get_bytes (concrete_byte_range (14_bytes, 1_byte)));
3896 4 : }
3897 :
3898 : /* Test type-punning uint32_t to bytes, using the target's endianness. */
3899 :
3900 : static void
3901 4 : test_uint32_t_to_bytes ()
3902 : {
3903 4 : symbolic::node_manager mgr;
3904 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3905 4 : auto &rmm = mgr.get_region_model_manager ();
3906 :
3907 4 : auto &uint32_0x12345678
3908 4 : = *rmm.get_or_create_int_cst (uint32_type_node, 0x12345678);
3909 4 : auto &bv_0x12345678 = bv_mgr.get_bit_vector_from_svalue (uint32_0x12345678);
3910 :
3911 4 : auto &uint8_0x12
3912 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x12);
3913 4 : auto &bv_0x12 = bv_mgr.get_bit_vector_from_svalue (uint8_0x12);
3914 :
3915 4 : auto &uint8_0x34
3916 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x34);
3917 4 : auto &bv_0x34 = bv_mgr.get_bit_vector_from_svalue (uint8_0x34);
3918 :
3919 4 : auto &uint8_0x56
3920 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x56);
3921 4 : auto &bv_0x56 = bv_mgr.get_bit_vector_from_svalue (uint8_0x56);
3922 :
3923 4 : auto &uint8_0x78
3924 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x78);
3925 4 : auto &bv_0x78 = bv_mgr.get_bit_vector_from_svalue (uint8_0x78);
3926 :
3927 4 : auto &bv_byte_0 = bv_0x12345678.get_byte_at_offset (0_bytes);
3928 4 : auto &bv_byte_1 = bv_0x12345678.get_byte_at_offset (1_byte);
3929 4 : auto &bv_byte_2 = bv_0x12345678.get_byte_at_offset (2_bytes);
3930 4 : auto &bv_byte_3 = bv_0x12345678.get_byte_at_offset (3_bytes);
3931 :
3932 4 : if (BYTES_BIG_ENDIAN)
3933 : {
3934 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_0, bv_0x12);
3935 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_1, bv_0x34);
3936 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_2, bv_0x56);
3937 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_3, bv_0x78);
3938 : }
3939 : else
3940 : {
3941 : /* Little-endian. */
3942 4 : if (!WORDS_BIG_ENDIAN)
3943 : {
3944 4 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_0, bv_0x78);
3945 4 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_1, bv_0x56);
3946 4 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_2, bv_0x34);
3947 4 : ASSERT_SAME_SYMBOLIC_NODE (bv_byte_3, bv_0x12);
3948 : }
3949 : }
3950 4 : }
3951 :
3952 : /* Test type-punning bytes to uint32_t, using the target's endianness. */
3953 :
3954 : static void
3955 4 : test_bytes_to_uint32_t ()
3956 : {
3957 4 : symbolic::node_manager mgr;
3958 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3959 4 : auto &rmm = mgr.get_region_model_manager ();
3960 :
3961 4 : auto &uint8_0x12
3962 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x12);
3963 4 : auto &bv_0x12 = bv_mgr.get_bit_vector_from_svalue (uint8_0x12);
3964 :
3965 4 : auto &uint8_0x34
3966 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x34);
3967 4 : auto &bv_0x34 = bv_mgr.get_bit_vector_from_svalue (uint8_0x34);
3968 :
3969 4 : auto &uint8_0x56
3970 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x56);
3971 4 : auto &bv_0x56 = bv_mgr.get_bit_vector_from_svalue (uint8_0x56);
3972 :
3973 4 : auto &uint8_0x78
3974 4 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x78);
3975 4 : auto &bv_0x78 = bv_mgr.get_bit_vector_from_svalue (uint8_0x78);
3976 :
3977 4 : auto &bytes
3978 4 : = bv_mgr.get_concat_bits ({&bv_0x12, &bv_0x34, &bv_0x56, &bv_0x78});
3979 :
3980 4 : const svalue *sval = rmm.get_svalue_from_bit_vector (uint32_type_node, bytes);
3981 :
3982 4 : const uint32_t expected_uint32 = (BYTES_BIG_ENDIAN
3983 : ? 0x12345678
3984 : : (WORDS_BIG_ENDIAN
3985 : ? 0x34127856
3986 : : 0x78563412));
3987 4 : ASSERT_SAME_SYMBOLIC_NODE
3988 : (*sval,
3989 : *rmm.get_or_create_int_cst (uint32_type_node, expected_uint32));
3990 4 : }
3991 :
3992 : static void
3993 4 : test_every_byte_value ()
3994 : {
3995 4 : symbolic::node_manager mgr;
3996 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3997 :
3998 4 : std::vector<const symbolic::bit_vector *> vec_of_every_byte_value;
3999 1028 : for (int i = 0; i < 256; ++i)
4000 1024 : vec_of_every_byte_value.push_back (&bv_mgr.get_uint8 (i));
4001 4 : auto &every_byte_value_bv
4002 4 : = bv_mgr.get_concat_bits (std::move (vec_of_every_byte_value));
4003 :
4004 4 : {
4005 4 : hexdump_options hexdump_opts;
4006 4 : hexdump_opts.m_show_binary = true;
4007 4 : hexdump_opts.m_show_hex = true;
4008 4 : hexdump_opts.m_show_ascii = false;
4009 :
4010 : /* Hexdump of first 8 bytes. */
4011 4 : {
4012 4 : pretty_printer pp;
4013 4 : every_byte_value_bv
4014 12 : .get_cropped_bytes (concrete_byte_range (0_bytes, 8_bytes))
4015 4 : .hexdump_to_pp (&pp, hexdump_opts);
4016 4 : ASSERT_STREQ
4017 : (pp_formatted_text (&pp),
4018 : ("+------------+-----------------------------------+-----------+\n"
4019 : "|[bytes 0..4)|00000000 10000000 01000000 11000000|00 01 02 03|\n"
4020 : "+------------+-----------------------------------+-----------+\n"
4021 : "|[bytes 4..8)|00100000 10100000 01100000 11100000|04 05 06 07|\n"
4022 : "+------------+-----------------------------------+-----------+\n"));
4023 4 : }
4024 :
4025 : /* Hexdump of last 8 bytes. */
4026 4 : {
4027 4 : pretty_printer pp;
4028 4 : every_byte_value_bv
4029 12 : .get_cropped_bytes (concrete_byte_range (248_bytes, 8_bytes))
4030 4 : .hexdump_to_pp (&pp, hexdump_opts);
4031 4 : ASSERT_STREQ
4032 : (pp_formatted_text (&pp),
4033 : ("+------------+-----------------------------------+-----------+\n"
4034 : "|[bytes 0..4)|00011111 10011111 01011111 11011111|f8 f9 fa fb|\n"
4035 : "+------------+-----------------------------------+-----------+\n"
4036 : "|[bytes 4..8)|00111111 10111111 01111111 11111111|fc fd fe ff|\n"
4037 : "+------------+-----------------------------------+-----------+\n"));
4038 4 : }
4039 4 : }
4040 4 : }
4041 :
4042 : /* Run all of the selftests within this file. */
4043 :
4044 : void
4045 4 : analyzer_symbolic_bit_vectors_cc_tests ()
4046 : {
4047 4 : test_maybe_set_irange_bitmask_from_concrete_tristate_vector ();
4048 4 : test_tristate ();
4049 4 : test_integer_constants ();
4050 4 : test_bytes ();
4051 4 : test_string_constants ();
4052 4 : test_raw_data_constant_1 ();
4053 4 : test_raw_data_constant_2 ();
4054 4 : test_raw_data_constant_empty ();
4055 4 : test_concat ();
4056 4 : test_cropped ();
4057 4 : test_named_test_bit_vector ();
4058 4 : test_poisoned ();
4059 4 : test_repeated ();
4060 4 : test_bit_vector_from_svalue ();
4061 4 : test_from_unfoldable_bit_contents ();
4062 4 : test_example_strcat ();
4063 4 : test_uint32_t_to_bytes ();
4064 4 : test_bytes_to_uint32_t ();
4065 4 : test_every_byte_value ();
4066 4 : }
4067 :
4068 : } // namespace selftest
4069 :
4070 : #endif /* CHECKING_P */
4071 :
4072 : } // namespace ana
4073 :
4074 : #endif /* #if ENABLE_ANALYZER */
|