gcc/ipa-modref-tree.c

   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);
  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
 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
 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 }