1 /* Data structure for the modref pass.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3 Contributed by David Cepelik and Jan Hubicka
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
26 #include "ipa-modref-tree.h"
34 test_insert_search_collapse ()
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
;
40 modref_tree
<alias_set_type
> *t
= new modref_tree
<alias_set_type
>(1, 2, 2);
41 ASSERT_FALSE (t
->every_base
);
43 /* Insert into an empty tree. */
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
);
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
);
57 ref_node
= base_node
->search (2);
58 ASSERT_NE (ref_node
, NULL
);
59 ASSERT_EQ (ref_node
->ref
, 2);
61 /* Insert when base exists but ref does not. */
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);
70 ref_node
= base_node
->search (3);
71 ASSERT_NE (ref_node
, NULL
);
73 /* Insert when base and ref exist, but access is not dominated by nor
74 dominates other accesses. */
76 ASSERT_EQ (t
->bases
->length (), 1);
77 ASSERT_EQ (t
->search (1), base_node
);
79 ref_node
= base_node
->search (2);
80 ASSERT_NE (ref_node
, NULL
);
82 /* Insert when base and ref exist and access is dominated. */
84 ASSERT_EQ (t
->search (1), base_node
);
85 ASSERT_EQ (base_node
->search (2), ref_node
);
87 /* Insert ref to trigger ref list collapse for base 1. */
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
);
95 /* Further inserts to collapsed ref list are ignored. */
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
);
103 /* Insert base to trigger base list collapse. */
105 ASSERT_TRUE (t
->every_base
);
106 ASSERT_EQ (t
->bases
, NULL
);
107 ASSERT_EQ (t
->search (1), NULL
);
109 /* Further inserts to collapsed base list are ignored. */
111 ASSERT_TRUE (t
->every_base
);
112 ASSERT_EQ (t
->bases
, NULL
);
113 ASSERT_EQ (t
->search (1), NULL
);
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
;
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
);
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
);
141 t1
->merge (t2
, NULL
);
143 ASSERT_FALSE (t1
->every_base
);
144 ASSERT_NE (t1
->bases
, NULL
);
145 ASSERT_EQ (t1
->bases
->length (), 3);
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);
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);
157 base_node
= t1
->search (3);
158 ASSERT_EQ (base_node
->refs
, NULL
);
159 ASSERT_TRUE (base_node
->every_ref
);
167 ipa_modref_tree_c_tests ()
169 test_insert_search_collapse ();
173 } // namespace selftest
178 gt_ggc_mx (modref_tree
< int >*const &tt
)
182 ggc_test_and_set_mark (tt
->bases
);
183 gt_ggc_mx (tt
->bases
);
188 gt_ggc_mx (modref_tree
< tree_node
* >*const &tt
)
192 ggc_test_and_set_mark (tt
->bases
);
193 gt_ggc_mx (tt
->bases
);
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 *) {}
202 void gt_ggc_mx (modref_base_node
<int>* &b
)
204 ggc_test_and_set_mark (b
);
207 ggc_test_and_set_mark (b
->refs
);
212 void gt_ggc_mx (modref_base_node
<tree_node
*>* &b
)
214 ggc_test_and_set_mark (b
);
217 ggc_test_and_set_mark (b
->refs
);
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 *) {}
229 void gt_ggc_mx (modref_ref_node
<int>* &r
)
231 ggc_test_and_set_mark (r
);
234 ggc_test_and_set_mark (r
->accesses
);
235 gt_ggc_mx (r
->accesses
);
239 void gt_ggc_mx (modref_ref_node
<tree_node
*>* &r
)
241 ggc_test_and_set_mark (r
);
244 ggc_test_and_set_mark (r
->accesses
);
245 gt_ggc_mx (r
->accesses
);
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 *) {}
256 void gt_ggc_mx (modref_access_node
&)