gcc/value-range-equiv.cc

   1 /* Support routines for value ranges with equivalences.
   2    Copyright (C) 2020-2022 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "ssa.h"
  27 #include "tree-pretty-print.h"
  28 #include "value-range-equiv.h"
  29
  30 value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv,
  31                                       value_range_kind kind)
  32 {
  33   m_equiv = NULL;
  34   set (min, max, equiv, kind);
  35 }
  36
  37 value_range_equiv::value_range_equiv (const value_range &other)
  38 {
  39   m_equiv = NULL;
  40   set (other.min(), other.max (), NULL, other.kind ());
  41 }
  42
  43 void
  44 value_range_equiv::set (tree min, tree max, bitmap equiv,
  45                         value_range_kind kind)
  46 {
  47   value_range::set (min, max, kind);
  48   set_equiv (equiv);
  49   if (flag_checking)
  50     check ();
  51 }
  52
  53 void
  54 value_range_equiv::set (tree min, tree max, value_range_kind kind)
  55 {
  56   set (min, max, m_equiv, kind);
  57 }
  58
  59 void
  60 value_range_equiv::set (tree val)
  61 {
  62   gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
  63   if (TREE_OVERFLOW_P (val))
  64     val = drop_tree_overflow (val);
  65   set (val, val);
  66 }
  67
  68 void
  69 value_range_equiv::set_undefined ()
  70 {
  71   set (NULL, NULL, NULL, VR_UNDEFINED);
  72 }
  73
  74 void
  75 value_range_equiv::set_varying (tree type)
  76 {
  77   value_range::set_varying (type);
  78   equiv_clear ();
  79 }
  80
  81 /* Like set, but keep the equivalences in place.  */
  82
  83 void
  84 value_range_equiv::update (tree min, tree max, value_range_kind kind)
  85 {
  86   set (min, max,
  87        (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind);
  88 }
  89
  90 /* Copy value_range in FROM into THIS while avoiding bitmap sharing.
  91
  92    Note: The code that avoids the bitmap sharing looks at the existing
  93    this->m_equiv, so this function cannot be used to initalize an
  94    object.  Use the constructors for initialization.  */
  95
  96 void
  97 value_range_equiv::deep_copy (const value_range_equiv *from)
  98 {
  99   set (from->min (), from->max (), from->m_equiv, from->kind ());
 100 }
 101
 102 void
 103 value_range_equiv::move (value_range_equiv *from)
 104 {
 105   set (from->min (), from->max (), NULL, from->kind ());
 106   m_equiv = from->m_equiv;
 107   from->m_equiv = NULL;
 108 }
 109
 110 void
 111 value_range_equiv::set_equiv (bitmap equiv)
 112 {
 113   if (undefined_p () || varying_p ())
 114     equiv = NULL;
 115   /* Since updating the equivalence set involves deep copying the
 116      bitmaps, only do it if absolutely necessary.
 117
 118      All equivalence bitmaps are allocated from the same obstack.  So
 119      we can use the obstack associated with EQUIV to allocate vr->equiv.  */
 120   if (m_equiv == NULL
 121       && equiv != NULL)
 122     m_equiv = BITMAP_ALLOC (equiv->obstack);
 123
 124   if (equiv != m_equiv)
 125     {
 126       if (equiv && !bitmap_empty_p (equiv))
 127         bitmap_copy (m_equiv, equiv);
 128       else
 129         bitmap_clear (m_equiv);
 130     }
 131 }
 132
 133 void
 134 value_range_equiv::check ()
 135 {
 136   value_range::verify_range ();
 137   switch (kind ())
 138     {
 139     case VR_UNDEFINED:
 140     case VR_VARYING:
 141       gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
 142     default:;
 143     }
 144 }
 145
 146 /* Return true if the bitmaps B1 and B2 are equal.  */
 147
 148 static bool
 149 vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 150 {
 151   return (b1 == b2
 152           || ((!b1 || bitmap_empty_p (b1))
 153               && (!b2 || bitmap_empty_p (b2)))
 154           || (b1 && b2
 155               && bitmap_equal_p (b1, b2)));
 156 }
 157
 158 /* Returns TRUE if THIS == OTHER.  Ignores the equivalence bitmap if
 159    IGNORE_EQUIVS is TRUE.  */
 160
 161 bool
 162 value_range_equiv::equal_p (const value_range_equiv &other,
 163                             bool ignore_equivs) const
 164 {
 165   return (value_range::operator== (other)
 166           && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv)));
 167 }
 168
 169 void
 170 value_range_equiv::equiv_clear ()
 171 {
 172   if (m_equiv)
 173     bitmap_clear (m_equiv);
 174 }
 175
 176 /* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence
 177    bitmap.  If no equivalence table has been created, OBSTACK is the
 178    obstack to use (NULL for the default obstack).
 179
 180    This is the central point where equivalence processing can be
 181    turned on/off.  */
 182
 183 void
 184 value_range_equiv::equiv_add (const_tree var,
 185                               const value_range_equiv *var_vr,
 186                               bitmap_obstack *obstack)
 187 {
 188   if (!m_equiv)
 189     m_equiv = BITMAP_ALLOC (obstack);
 190   unsigned ver = SSA_NAME_VERSION (var);
 191   bitmap_set_bit (m_equiv, ver);
 192   if (var_vr && var_vr->m_equiv)
 193     bitmap_ior_into (m_equiv, var_vr->m_equiv);
 194 }
 195
 196 void
 197 value_range_equiv::legacy_verbose_intersect (const value_range_equiv *other)
 198 {
 199   if (dump_file && (dump_flags & TDF_DETAILS))
 200     {
 201       fprintf (dump_file, "Intersecting\n  ");
 202       dump_value_range (dump_file, this);
 203       fprintf (dump_file, "\nand\n  ");
 204       dump_value_range (dump_file, other);
 205       fprintf (dump_file, "\n");
 206     }
 207
 208   /* If THIS is varying we want to pick up equivalences from OTHER.
 209      Just special-case this here rather than trying to fixup after the
 210      fact.  */
 211   if (this->varying_p ())
 212     this->deep_copy (other);
 213   else
 214     {
 215       legacy_intersect (this, other);
 216       if (varying_p () || undefined_p ())
 217         equiv_clear ();
 218
 219       /* If the result is VR_UNDEFINED there is no need to mess with
 220          equivalencies.  */
 221       if (!undefined_p ())
 222         {
 223           /* The resulting set of equivalences for range intersection
 224              is the union of the two sets.  */
 225           if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
 226             bitmap_ior_into (m_equiv, other->m_equiv);
 227           else if (other->m_equiv && !m_equiv)
 228             {
 229               /* All equivalence bitmaps are allocated from the same
 230                  obstack.  So we can use the obstack associated with
 231                  VR to allocate this->m_equiv.  */
 232               m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
 233               bitmap_copy (m_equiv, other->m_equiv);
 234             }
 235         }
 236     }
 237
 238   if (dump_file && (dump_flags & TDF_DETAILS))
 239     {
 240       fprintf (dump_file, "to\n  ");
 241       dump_value_range (dump_file, this);
 242       fprintf (dump_file, "\n");
 243     }
 244 }
 245
 246 void
 247 value_range_equiv::legacy_verbose_union_ (const value_range_equiv *other)
 248 {
 249   if (dump_file && (dump_flags & TDF_DETAILS))
 250     {
 251       fprintf (dump_file, "Meeting\n  ");
 252       dump_value_range (dump_file, this);
 253       fprintf (dump_file, "\nand\n  ");
 254       dump_value_range (dump_file, other);
 255       fprintf (dump_file, "\n");
 256     }
 257
 258   /* If THIS is undefined we want to pick up equivalences from OTHER.
 259      Just special-case this here rather than trying to fixup after the fact.  */
 260   if (this->undefined_p ())
 261     this->deep_copy (other);
 262   else
 263     {
 264       legacy_union (this, other);
 265       if (varying_p () || undefined_p ())
 266         equiv_clear ();
 267
 268       /* The resulting set of equivalences is always the intersection of
 269          the two sets.  */
 270       if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv)
 271         bitmap_and_into (this->m_equiv, other->m_equiv);
 272       else if (this->m_equiv && !other->m_equiv)
 273         bitmap_clear (this->m_equiv);
 274     }
 275
 276   if (dump_file && (dump_flags & TDF_DETAILS))
 277     {
 278       fprintf (dump_file, "to\n  ");
 279       dump_value_range (dump_file, this);
 280       fprintf (dump_file, "\n");
 281     }
 282 }
 283
 284 void
 285 value_range_equiv::dump (FILE *file) const
 286 {
 287   value_range::dump (file);
 288   if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE)
 289       && m_equiv)
 290     {
 291       bitmap_iterator bi;
 292       unsigned i, c = 0;
 293
 294       fprintf (file, "  EQUIVALENCES: { ");
 295       EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi)
 296         {
 297           print_generic_expr (file, ssa_name (i));
 298           fprintf (file, " ");
 299           c++;
 300         }
 301       fprintf (file, "} (%u elements)", c);
 302     }
 303 }
 304
 305 void
 306 value_range_equiv::dump () const
 307 {
 308   dump (stderr);
 309 }
 310
 311 void
 312 dump_value_range (FILE *file, const value_range_equiv *vr)
 313 {
 314   if (!vr)
 315     fprintf (file, "[]");
 316   else
 317     vr->dump (file);
 318 }
 319
 320 DEBUG_FUNCTION void
 321 debug (const value_range_equiv *vr)
 322 {
 323   dump_value_range (stderr, vr);
 324 }
 325
 326 DEBUG_FUNCTION void
 327 debug (const value_range_equiv &vr)
 328 {
 329   dump_value_range (stderr, &vr);
 330 }