1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/*
Execute symbolically all paths of the function. Iterate loops only once.
Copyright (C) 2006-2022 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#ifndef GCC_EXECUTE_ALL_PATHS_H
#define GCC_EXECUTE_ALL_PATHS_H
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-niter.h"
#include "cfgloop.h"
#include "gimple-range.h"
#include "tree-scalar-evolution.h"
#include "hwint.h"
#include "function.h"
#include "sym-exec/state.h"
class crc_symb_execution {
private:
/* A vector of states to keep the current state of each executed path. */
vec<state*> states;
/* A vector of final states
to keep the returned_value and path conditions. */
vec<state*> final_states;
/* Assign symbolic values to the arguments of the function
and keep in the state. */
static bool make_symbolic_func_args_and_sizes (function *, state *);
/* Add declared ssa variables to the state. */
static bool add_function_local_ssa_vars (function *, state *);
bool execute_assign_statement (const gassign *);
/* Add next basic blocks of the conditional block
for the execution path into the stack. */
void add_next_bbs (basic_block, state *, auto_vec<edge, 20>&);
/* Keep conditions depending on symbolic variables in the states. */
static bool add_condition (const gcond*, state*, state*);
/* Create new state for true and false branch.
Keep conditions in new created states. */
bool resolve_condition (const gcond*, auto_vec<edge, 20>&);
/* Keep the calculated value of the return value
and the conditions of the executed path. */
bool keep_return_val_and_conditions (const greturn*);
/* Execute gimple statements of the basic block.
Keeping values of variables in the state. */
bool execute_bb_gimple_statements (basic_block, auto_vec<edge, 20>&);
/* Assign values of phi instruction to its result.
Keep updated values in the state. */
bool execute_bb_phi_statements (basic_block, edge);
/* Execute all statements of the basic block.
Keeping values of variables in the state. */
bool execute_bb_statements (basic_block, edge, auto_vec<edge, 20>&);
/* Traverse function fun's all paths from the first basic block to the last.
Each time iterate loops only once.
Symbolically execute statements of each path. */
bool traverse_function (function *);
/* Execute the loop, which calculates crc with initial values,
to calculate the polynomial. */
bool execute_crc_loop (loop *, gphi *, gphi *, bool);
/* Returns true if the state matches the LFSR, otherwise - false. */
bool state_matches_lfsr (const vec<value*> &, const vec<value*> &);
public:
/* Symbolically execute the function and keep final states. */
bool execute_function (function *);
/* Returns calculated polynomial by executing the loop
with concrete values. */
vec<value*> * extract_poly_and_create_lfsr (loop *, gphi *, gphi *, bool);
/* Returns true if all states match the LFSR, otherwise - false. */
bool states_match_lfsr (vec<value*> *lfsr);
crc_symb_execution ()
{
/* Reserve memory for the vectors of states. */
states.create (30);
final_states.create (30);
}
~crc_symb_execution ()
{
/* Free memory. */
states.release ();
final_states.release ();
}
};
#endif //GCC_EXECUTE_ALL_PATHS_H
|
