]>
Commit | Line | Data |
---|---|---|
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 | |
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, false); | |
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, false); | |
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, false); | |
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, false); | |
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, false); | |
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, false); | |
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, 0, a, false); | |
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, false); | |
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 | |
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, false); | |
127 | t1->insert (1, 2, a, false); | |
128 | t1->insert (1, 3, a, false); | |
129 | t1->insert (2, 1, a, false); | |
130 | t1->insert (3, 1, a, false); | |
131 | ||
132 | t2 = new modref_tree<alias_set_type>(10, 10, 10); | |
133 | t2->insert (1, 2, a, false); | |
134 | t2->insert (1, 3, a, false); | |
135 | t2->insert (1, 4, a, false); | |
136 | t2->insert (3, 2, a, false); | |
137 | t2->insert (3, 3, a, false); | |
138 | t2->insert (3, 4, a, false); | |
139 | t2->insert (3, 5, a, false); | |
140 | ||
141 | t1->merge (t2, NULL, false); | |
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 | |
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 | |
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 | |
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 | ||
197 | void gt_pch_nx (modref_tree<int>* const&) {} | |
198 | void gt_pch_nx (modref_tree<tree_node*>* const&) {} | |
199 | void gt_pch_nx (modref_tree<int>* const&, gt_pointer_operator, void *) {} | |
200 | void gt_pch_nx (modref_tree<tree_node*>* const&, gt_pointer_operator, void *) {} | |
201 | ||
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 | ||
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 | ||
224 | void gt_pch_nx (modref_base_node<int>*) {} | |
225 | void gt_pch_nx (modref_base_node<tree_node*>*) {} | |
226 | void gt_pch_nx (modref_base_node<int>*, gt_pointer_operator, void *) {} | |
227 | void gt_pch_nx (modref_base_node<tree_node*>*, gt_pointer_operator, void *) {} | |
228 | ||
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 | ||
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 | ||
251 | void gt_pch_nx (modref_ref_node<int>* ) {} | |
252 | void gt_pch_nx (modref_ref_node<tree_node*>*) {} | |
253 | void gt_pch_nx (modref_ref_node<int>*, gt_pointer_operator, void *) {} | |
254 | void gt_pch_nx (modref_ref_node<tree_node*>*, gt_pointer_operator, void *) {} | |
255 | ||
256 | void gt_ggc_mx (modref_access_node &) | |
257 | { | |
258 | } |