1 /* Data structure for the modref pass.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3 Contributed by David Cepelik and Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 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 "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "tree.h"
26 #include "ipa-modref-tree.h"
27 #include "selftest.h"
28
29 #if CHECKING_P
30
31 namespace selftest {
32
33 static void
test_insert_search_collapse()34 test_insert_search_collapse ()
35 {
36 modref_base_node<alias_set_type> *base_node;
37 modref_ref_node<alias_set_type> *ref_node;
38 modref_access_node a = unspecified_modref_access_node;
39
40 modref_tree<alias_set_type> *t = new modref_tree<alias_set_type>(1, 2, 2);
41 ASSERT_FALSE (t->every_base);
42
43 /* Insert into an empty tree. */
44 t->insert (1, 2, a);
45 ASSERT_NE (t->bases, NULL);
46 ASSERT_EQ (t->bases->length (), 1);
47 ASSERT_FALSE (t->every_base);
48 ASSERT_EQ (t->search (2), NULL);
49
50 base_node = t->search (1);
51 ASSERT_NE (base_node, NULL);
52 ASSERT_EQ (base_node->base, 1);
53 ASSERT_NE (base_node->refs, NULL);
54 ASSERT_EQ (base_node->refs->length (), 1);
55 ASSERT_EQ (base_node->search (1), NULL);
56
57 ref_node = base_node->search (2);
58 ASSERT_NE (ref_node, NULL);
59 ASSERT_EQ (ref_node->ref, 2);
60
61 /* Insert when base exists but ref does not. */
62 t->insert (1, 3, a);
63 ASSERT_NE (t->bases, NULL);
64 ASSERT_EQ (t->bases->length (), 1);
65 ASSERT_EQ (t->search (1), base_node);
66 ASSERT_EQ (t->search (2), NULL);
67 ASSERT_NE (base_node->refs, NULL);
68 ASSERT_EQ (base_node->refs->length (), 2);
69
70 ref_node = base_node->search (3);
71 ASSERT_NE (ref_node, NULL);
72
73 /* Insert when base and ref exist, but access is not dominated by nor
74 dominates other accesses. */
75 t->insert (1, 2, a);
76 ASSERT_EQ (t->bases->length (), 1);
77 ASSERT_EQ (t->search (1), base_node);
78
79 ref_node = base_node->search (2);
80 ASSERT_NE (ref_node, NULL);
81
82 /* Insert when base and ref exist and access is dominated. */
83 t->insert (1, 2, a);
84 ASSERT_EQ (t->search (1), base_node);
85 ASSERT_EQ (base_node->search (2), ref_node);
86
87 /* Insert ref to trigger ref list collapse for base 1. */
88 t->insert (1, 4, a);
89 ASSERT_EQ (t->search (1), base_node);
90 ASSERT_EQ (base_node->refs, NULL);
91 ASSERT_EQ (base_node->search (2), NULL);
92 ASSERT_EQ (base_node->search (3), NULL);
93 ASSERT_TRUE (base_node->every_ref);
94
95 /* Further inserts to collapsed ref list are ignored. */
96 t->insert (1, 5, a);
97 ASSERT_EQ (t->search (1), base_node);
98 ASSERT_EQ (base_node->refs, NULL);
99 ASSERT_EQ (base_node->search (2), NULL);
100 ASSERT_EQ (base_node->search (3), NULL);
101 ASSERT_TRUE (base_node->every_ref);
102
103 /* Insert base to trigger base list collapse. */
104 t->insert (5, 6, a);
105 ASSERT_TRUE (t->every_base);
106 ASSERT_EQ (t->bases, NULL);
107 ASSERT_EQ (t->search (1), NULL);
108
109 /* Further inserts to collapsed base list are ignored. */
110 t->insert (7, 8, a);
111 ASSERT_TRUE (t->every_base);
112 ASSERT_EQ (t->bases, NULL);
113 ASSERT_EQ (t->search (1), NULL);
114
115 delete t;
116 }
117
118 static void
test_merge()119 test_merge ()
120 {
121 modref_tree<alias_set_type> *t1, *t2;
122 modref_base_node<alias_set_type> *base_node;
123 modref_access_node a = unspecified_modref_access_node;
124
125 t1 = new modref_tree<alias_set_type>(3, 4, 1);
126 t1->insert (1, 1, a);
127 t1->insert (1, 2, a);
128 t1->insert (1, 3, a);
129 t1->insert (2, 1, a);
130 t1->insert (3, 1, a);
131
132 t2 = new modref_tree<alias_set_type>(10, 10, 10);
133 t2->insert (1, 2, a);
134 t2->insert (1, 3, a);
135 t2->insert (1, 4, a);
136 t2->insert (3, 2, a);
137 t2->insert (3, 3, a);
138 t2->insert (3, 4, a);
139 t2->insert (3, 5, a);
140
141 t1->merge (t2, NULL);
142
143 ASSERT_FALSE (t1->every_base);
144 ASSERT_NE (t1->bases, NULL);
145 ASSERT_EQ (t1->bases->length (), 3);
146
147 base_node = t1->search (1);
148 ASSERT_NE (base_node->refs, NULL);
149 ASSERT_FALSE (base_node->every_ref);
150 ASSERT_EQ (base_node->refs->length (), 4);
151
152 base_node = t1->search (2);
153 ASSERT_NE (base_node->refs, NULL);
154 ASSERT_FALSE (base_node->every_ref);
155 ASSERT_EQ (base_node->refs->length (), 1);
156
157 base_node = t1->search (3);
158 ASSERT_EQ (base_node->refs, NULL);
159 ASSERT_TRUE (base_node->every_ref);
160
161 delete t1;
162 delete t2;
163 }
164
165
166 void
ipa_modref_tree_c_tests()167 ipa_modref_tree_c_tests ()
168 {
169 test_insert_search_collapse ();
170 test_merge ();
171 }
172
173 } // namespace selftest
174
175 #endif
176
177 void
gt_ggc_mx(modref_tree<int> * const & tt)178 gt_ggc_mx (modref_tree < int >*const &tt)
179 {
180 if (tt->bases)
181 {
182 ggc_test_and_set_mark (tt->bases);
183 gt_ggc_mx (tt->bases);
184 }
185 }
186
187 void
gt_ggc_mx(modref_tree<tree_node * > * const & tt)188 gt_ggc_mx (modref_tree < tree_node * >*const &tt)
189 {
190 if (tt->bases)
191 {
192 ggc_test_and_set_mark (tt->bases);
193 gt_ggc_mx (tt->bases);
194 }
195 }
196
gt_pch_nx(modref_tree<int> * const &)197 void gt_pch_nx (modref_tree<int>* const&) {}
gt_pch_nx(modref_tree<tree_node * > * const &)198 void gt_pch_nx (modref_tree<tree_node*>* const&) {}
gt_pch_nx(modref_tree<int> * const &,gt_pointer_operator,void *)199 void gt_pch_nx (modref_tree<int>* const&, gt_pointer_operator, void *) {}
gt_pch_nx(modref_tree<tree_node * > * const &,gt_pointer_operator,void *)200 void gt_pch_nx (modref_tree<tree_node*>* const&, gt_pointer_operator, void *) {}
201
gt_ggc_mx(modref_base_node<int> * & b)202 void gt_ggc_mx (modref_base_node<int>* &b)
203 {
204 ggc_test_and_set_mark (b);
205 if (b->refs)
206 {
207 ggc_test_and_set_mark (b->refs);
208 gt_ggc_mx (b->refs);
209 }
210 }
211
gt_ggc_mx(modref_base_node<tree_node * > * & b)212 void gt_ggc_mx (modref_base_node<tree_node*>* &b)
213 {
214 ggc_test_and_set_mark (b);
215 if (b->refs)
216 {
217 ggc_test_and_set_mark (b->refs);
218 gt_ggc_mx (b->refs);
219 }
220 if (b->base)
221 gt_ggc_mx (b->base);
222 }
223
gt_pch_nx(modref_base_node<int> *)224 void gt_pch_nx (modref_base_node<int>*) {}
gt_pch_nx(modref_base_node<tree_node * > *)225 void gt_pch_nx (modref_base_node<tree_node*>*) {}
gt_pch_nx(modref_base_node<int> *,gt_pointer_operator,void *)226 void gt_pch_nx (modref_base_node<int>*, gt_pointer_operator, void *) {}
gt_pch_nx(modref_base_node<tree_node * > *,gt_pointer_operator,void *)227 void gt_pch_nx (modref_base_node<tree_node*>*, gt_pointer_operator, void *) {}
228
gt_ggc_mx(modref_ref_node<int> * & r)229 void gt_ggc_mx (modref_ref_node<int>* &r)
230 {
231 ggc_test_and_set_mark (r);
232 if (r->accesses)
233 {
234 ggc_test_and_set_mark (r->accesses);
235 gt_ggc_mx (r->accesses);
236 }
237 }
238
gt_ggc_mx(modref_ref_node<tree_node * > * & r)239 void gt_ggc_mx (modref_ref_node<tree_node*>* &r)
240 {
241 ggc_test_and_set_mark (r);
242 if (r->accesses)
243 {
244 ggc_test_and_set_mark (r->accesses);
245 gt_ggc_mx (r->accesses);
246 }
247 if (r->ref)
248 gt_ggc_mx (r->ref);
249 }
250
gt_pch_nx(modref_ref_node<int> *)251 void gt_pch_nx (modref_ref_node<int>* ) {}
gt_pch_nx(modref_ref_node<tree_node * > *)252 void gt_pch_nx (modref_ref_node<tree_node*>*) {}
gt_pch_nx(modref_ref_node<int> *,gt_pointer_operator,void *)253 void gt_pch_nx (modref_ref_node<int>*, gt_pointer_operator, void *) {}
gt_pch_nx(modref_ref_node<tree_node * > *,gt_pointer_operator,void *)254 void gt_pch_nx (modref_ref_node<tree_node*>*, gt_pointer_operator, void *) {}
255
gt_ggc_mx(modref_access_node &)256 void gt_ggc_mx (modref_access_node &)
257 {
258 }
259