blob: 64e57f52147de589da5702e3cb82bc1e37b697ec [file] [log] [blame]
/* Data structure for the modref pass.
Copyright (C) 2020-2021 Free Software Foundation, Inc.
Contributed by David Cepelik and Jan Hubicka
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/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "ipa-modref-tree.h"
#include "selftest.h"
#if CHECKING_P
namespace selftest {
static void
test_insert_search_collapse ()
{
modref_base_node<alias_set_type> *base_node;
modref_ref_node<alias_set_type> *ref_node;
modref_access_node a = unspecified_modref_access_node;
modref_tree<alias_set_type> *t = new modref_tree<alias_set_type>(1, 2, 2);
ASSERT_FALSE (t->every_base);
/* Insert into an empty tree. */
t->insert (1, 2, a);
ASSERT_NE (t->bases, NULL);
ASSERT_EQ (t->bases->length (), 1);
ASSERT_FALSE (t->every_base);
ASSERT_EQ (t->search (2), NULL);
base_node = t->search (1);
ASSERT_NE (base_node, NULL);
ASSERT_EQ (base_node->base, 1);
ASSERT_NE (base_node->refs, NULL);
ASSERT_EQ (base_node->refs->length (), 1);
ASSERT_EQ (base_node->search (1), NULL);
ref_node = base_node->search (2);
ASSERT_NE (ref_node, NULL);
ASSERT_EQ (ref_node->ref, 2);
/* Insert when base exists but ref does not. */
t->insert (1, 3, a);
ASSERT_NE (t->bases, NULL);
ASSERT_EQ (t->bases->length (), 1);
ASSERT_EQ (t->search (1), base_node);
ASSERT_EQ (t->search (2), NULL);
ASSERT_NE (base_node->refs, NULL);
ASSERT_EQ (base_node->refs->length (), 2);
ref_node = base_node->search (3);
ASSERT_NE (ref_node, NULL);
/* Insert when base and ref exist, but access is not dominated by nor
dominates other accesses. */
t->insert (1, 2, a);
ASSERT_EQ (t->bases->length (), 1);
ASSERT_EQ (t->search (1), base_node);
ref_node = base_node->search (2);
ASSERT_NE (ref_node, NULL);
/* Insert when base and ref exist and access is dominated. */
t->insert (1, 2, a);
ASSERT_EQ (t->search (1), base_node);
ASSERT_EQ (base_node->search (2), ref_node);
/* Insert ref to trigger ref list collapse for base 1. */
t->insert (1, 4, a);
ASSERT_EQ (t->search (1), base_node);
ASSERT_EQ (base_node->refs, NULL);
ASSERT_EQ (base_node->search (2), NULL);
ASSERT_EQ (base_node->search (3), NULL);
ASSERT_TRUE (base_node->every_ref);
/* Further inserts to collapsed ref list are ignored. */
t->insert (1, 5, a);
ASSERT_EQ (t->search (1), base_node);
ASSERT_EQ (base_node->refs, NULL);
ASSERT_EQ (base_node->search (2), NULL);
ASSERT_EQ (base_node->search (3), NULL);
ASSERT_TRUE (base_node->every_ref);
/* Insert base to trigger base list collapse. */
t->insert (5, 6, a);
ASSERT_TRUE (t->every_base);
ASSERT_EQ (t->bases, NULL);
ASSERT_EQ (t->search (1), NULL);
/* Further inserts to collapsed base list are ignored. */
t->insert (7, 8, a);
ASSERT_TRUE (t->every_base);
ASSERT_EQ (t->bases, NULL);
ASSERT_EQ (t->search (1), NULL);
delete t;
}
static void
test_merge ()
{
modref_tree<alias_set_type> *t1, *t2;
modref_base_node<alias_set_type> *base_node;
modref_access_node a = unspecified_modref_access_node;
t1 = new modref_tree<alias_set_type>(3, 4, 1);
t1->insert (1, 1, a);
t1->insert (1, 2, a);
t1->insert (1, 3, a);
t1->insert (2, 1, a);
t1->insert (3, 1, a);
t2 = new modref_tree<alias_set_type>(10, 10, 10);
t2->insert (1, 2, a);
t2->insert (1, 3, a);
t2->insert (1, 4, a);
t2->insert (3, 2, a);
t2->insert (3, 3, a);
t2->insert (3, 4, a);
t2->insert (3, 5, a);
t1->merge (t2, NULL);
ASSERT_FALSE (t1->every_base);
ASSERT_NE (t1->bases, NULL);
ASSERT_EQ (t1->bases->length (), 3);
base_node = t1->search (1);
ASSERT_NE (base_node->refs, NULL);
ASSERT_FALSE (base_node->every_ref);
ASSERT_EQ (base_node->refs->length (), 4);
base_node = t1->search (2);
ASSERT_NE (base_node->refs, NULL);
ASSERT_FALSE (base_node->every_ref);
ASSERT_EQ (base_node->refs->length (), 1);
base_node = t1->search (3);
ASSERT_EQ (base_node->refs, NULL);
ASSERT_TRUE (base_node->every_ref);
delete t1;
delete t2;
}
void
ipa_modref_tree_c_tests ()
{
test_insert_search_collapse ();
test_merge ();
}
} // namespace selftest
#endif
void
gt_ggc_mx (modref_tree < int >*const &tt)
{
if (tt->bases)
{
ggc_test_and_set_mark (tt->bases);
gt_ggc_mx (tt->bases);
}
}
void
gt_ggc_mx (modref_tree < tree_node * >*const &tt)
{
if (tt->bases)
{
ggc_test_and_set_mark (tt->bases);
gt_ggc_mx (tt->bases);
}
}
void gt_pch_nx (modref_tree<int>* const&) {}
void gt_pch_nx (modref_tree<tree_node*>* const&) {}
void gt_pch_nx (modref_tree<int>* const&, gt_pointer_operator, void *) {}
void gt_pch_nx (modref_tree<tree_node*>* const&, gt_pointer_operator, void *) {}
void gt_ggc_mx (modref_base_node<int>* &b)
{
ggc_test_and_set_mark (b);
if (b->refs)
{
ggc_test_and_set_mark (b->refs);
gt_ggc_mx (b->refs);
}
}
void gt_ggc_mx (modref_base_node<tree_node*>* &b)
{
ggc_test_and_set_mark (b);
if (b->refs)
{
ggc_test_and_set_mark (b->refs);
gt_ggc_mx (b->refs);
}
if (b->base)
gt_ggc_mx (b->base);
}
void gt_pch_nx (modref_base_node<int>*) {}
void gt_pch_nx (modref_base_node<tree_node*>*) {}
void gt_pch_nx (modref_base_node<int>*, gt_pointer_operator, void *) {}
void gt_pch_nx (modref_base_node<tree_node*>*, gt_pointer_operator, void *) {}
void gt_ggc_mx (modref_ref_node<int>* &r)
{
ggc_test_and_set_mark (r);
if (r->accesses)
{
ggc_test_and_set_mark (r->accesses);
gt_ggc_mx (r->accesses);
}
}
void gt_ggc_mx (modref_ref_node<tree_node*>* &r)
{
ggc_test_and_set_mark (r);
if (r->accesses)
{
ggc_test_and_set_mark (r->accesses);
gt_ggc_mx (r->accesses);
}
if (r->ref)
gt_ggc_mx (r->ref);
}
void gt_pch_nx (modref_ref_node<int>* ) {}
void gt_pch_nx (modref_ref_node<tree_node*>*) {}
void gt_pch_nx (modref_ref_node<int>*, gt_pointer_operator, void *) {}
void gt_pch_nx (modref_ref_node<tree_node*>*, gt_pointer_operator, void *) {}
void gt_ggc_mx (modref_access_node &)
{
}