Line data Source code
1 : /* Measuring the complexity of symbolic nodes.
2 : Copyright (C) 2020-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 "options.h"
24 : #include "cgraph.h"
25 : #include "cfg.h"
26 : #include "digraph.h"
27 :
28 : #include "analyzer/analyzer-logging.h"
29 : #include "analyzer/call-string.h"
30 : #include "analyzer/program-point.h"
31 : #include "analyzer/store.h"
32 : #include "analyzer/complexity.h"
33 : #include "analyzer/svalue.h"
34 : #include "analyzer/region.h"
35 :
36 : #include "selftest.h"
37 :
38 : #if ENABLE_ANALYZER
39 :
40 : namespace ana {
41 :
42 : /* struct complexity. */
43 :
44 : /* Get complexity for a new node that references NODE
45 : (the complexity of NODE, plus one for the new node). */
46 :
47 1281099 : complexity::complexity (const symbolic::node &node)
48 1281099 : : m_num_nodes (node.get_complexity ().m_num_nodes + 1),
49 1281099 : m_max_depth (node.get_complexity ().m_max_depth + 1)
50 : {
51 1281099 : }
52 :
53 : /* Get complexity for a new node that references REG
54 : (the complexity of REG, plus one for the new node). */
55 :
56 308544 : complexity::complexity (const region *reg)
57 308544 : : m_num_nodes (reg->get_complexity ().m_num_nodes + 1),
58 308544 : m_max_depth (reg->get_complexity ().m_max_depth + 1)
59 : {
60 308544 : }
61 :
62 : /* Get complexity for a new node that references SVAL.
63 : (the complexity of SVAL, plus one for the new node). */
64 :
65 42502 : complexity::complexity (const svalue *sval)
66 42502 : : m_num_nodes (sval->get_complexity ().m_num_nodes + 1),
67 42502 : m_max_depth (sval->get_complexity ().m_max_depth + 1)
68 : {
69 42502 : }
70 :
71 : /* Get complexity for a new node that references nodes with complexity
72 : C1 and C2. */
73 :
74 : complexity
75 109761 : complexity::from_pair (const complexity &c1, const complexity &c2)
76 : {
77 219522 : return complexity (c1.m_num_nodes + c2.m_num_nodes + 1,
78 109761 : MAX (c1.m_max_depth, c2.m_max_depth) + 1);
79 : }
80 :
81 : /* Get complexity for a new node that references the svalues in VEC. */
82 :
83 : complexity
84 324 : complexity::from_vec_svalue (const vec<const svalue *> &vec)
85 : {
86 324 : unsigned num_nodes = 0;
87 324 : unsigned max_depth = 0;
88 1317 : for (auto iter_sval : vec)
89 : {
90 409 : const complexity &iter_c = iter_sval->get_complexity ();
91 409 : num_nodes += iter_c.m_num_nodes;
92 409 : max_depth = MAX (max_depth, iter_c.m_max_depth);
93 : }
94 324 : return complexity (num_nodes + 1, max_depth + 1);
95 : }
96 :
97 : /* Get complexity for a new node which has children with overall
98 : complexity CHILD_COMPLEXITIES. */
99 :
100 : complexity
101 80252 : complexity::from_child_complexities (const complexity &child_complexities)
102 : {
103 : /* One extra node for the node itself; one more level of depth. */
104 80252 : return complexity (child_complexities.m_num_nodes + 1,
105 80252 : child_complexities.m_max_depth + 1);
106 : }
107 :
108 : /* The sum of two complexity instances is the sum of their
109 : numbers of nodes and the maximum of the maxima of their depths. */
110 :
111 : complexity
112 119510 : complexity::operator+ (const complexity &other) const
113 : {
114 119510 : return complexity (m_num_nodes + other.m_num_nodes,
115 119510 : std::max (m_max_depth, other.m_max_depth));
116 : }
117 :
118 : complexity &
119 102535 : complexity::operator+= (const complexity &other)
120 : {
121 102535 : *this = *this + other;
122 102535 : return *this;
123 : }
124 :
125 : #if CHECKING_P
126 :
127 : namespace selftest {
128 :
129 : void
130 4 : analyzer_complexity_cc_tests ()
131 : {
132 8 : ASSERT_EQ (complexity (1, 1) + complexity (1, 1),
133 : complexity (2, 1));
134 :
135 8 : ASSERT_EQ (complexity (3, 2) + complexity (3, 1),
136 : complexity (6, 2));
137 :
138 8 : ASSERT_EQ (complexity::from_child_complexities (complexity (3, 2)),
139 : complexity (4, 3));
140 4 : }
141 :
142 : } // namespace selftest
143 :
144 : #endif /* CHECKING_P */
145 :
146 :
147 : } // namespace ana
148 :
149 : #endif /* #if ENABLE_ANALYZER */
|