gcc/value-range-equiv.cc

   1 /* Support routines for value ranges with equivalences.
   2    Copyright (C) 2020-2021 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 val)
  55 {
  56   gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
  57   if (TREE_OVERFLOW_P (val))
  58     val = drop_tree_overflow (val);
  59   set (val, val);
  60 }
  61
  62 void
  63 value_range_equiv::set_undefined ()
  64 {
  65   set (NULL, NULL, NULL, VR_UNDEFINED);
  66 }
  67
  68 void
  69 value_range_equiv::set_varying (tree type)
  70 {
  71   value_range::set_varying (type);
  72   equiv_clear ();
  73 }
  74
  75 /* Like set, but keep the equivalences in place.  */
  76
  77 void
  78 value_range_equiv::update (tree min, tree max, value_range_kind kind)
  79 {
  80   set (min, max,
  81        (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind);
  82 }
  83
  84 /* Copy value_range in FROM into THIS while avoiding bitmap sharing.
  85
  86    Note: The code that avoids the bitmap sharing looks at the existing
  87    this->m_equiv, so this function cannot be used to initalize an
  88    object.  Use the constructors for initialization.  */
  89
  90 void
  91 value_range_equiv::deep_copy (const value_range_equiv *from)
  92 {
  93   set (from->min (), from->max (), from->m_equiv, from->kind ());
  94 }
  95
  96 void
  97 value_range_equiv::move (value_range_equiv *from)
  98 {
  99   set (from->min (), from->max (), NULL, from->kind ());
 100   m_equiv = from->m_equiv;
 101   from->m_equiv = NULL;
 102 }
 103
 104 void
 105 value_range_equiv::set_equiv (bitmap equiv)
 106 {
 107   if (undefined_p () || varying_p ())
 108     equiv = NULL;
 109   /* Since updating the equivalence set involves deep copying the
 110      bitmaps, only do it if absolutely necessary.
 111
 112      All equivalence bitmaps are allocated from the same obstack.  So
 113      we can use the obstack associated with EQUIV to allocate vr->equiv.  */
 114   if (m_equiv == NULL
 115       && equiv != NULL)
 116     m_equiv = BITMAP_ALLOC (equiv->obstack);
 117
 118   if (equiv != m_equiv)
 119     {
 120       if (equiv && !bitmap_empty_p (equiv))
 121         bitmap_copy (m_equiv, equiv);
 122       else
 123         bitmap_clear (m_equiv);
 124     }
 125 }
 126
 127 void
 128 value_range_equiv::check ()
 129 {
 130   value_range::verify_range ();
 131   switch (kind ())
 132     {
 133     case VR_UNDEFINED:
 134     case VR_VARYING:
 135       gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
 136     default:;
 137     }
 138 }
 139
 140 /* Return true if the bitmaps B1 and B2 are equal.  */
 141
 142 static bool
 143 vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 144 {
 145   return (b1 == b2
 146           || ((!b1 || bitmap_empty_p (b1))
 147               && (!b2 || bitmap_empty_p (b2)))
 148           || (b1 && b2
 149               && bitmap_equal_p (b1, b2)));
 150 }
 151
 152 /* Returns TRUE if THIS == OTHER.  Ignores the equivalence bitmap if
 153    IGNORE_EQUIVS is TRUE.  */
 154
 155 bool
 156 value_range_equiv::equal_p (const value_range_equiv &other,
 157                             bool ignore_equivs) const
 158 {
 159   return (value_range::equal_p (other)
 160           && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv)));
 161 }
 162
 163 void
 164 value_range_equiv::equiv_clear ()
 165 {
 166   if (m_equiv)
 167     bitmap_clear (m_equiv);
 168 }
 169
 170 /* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence
 171    bitmap.  If no equivalence table has been created, OBSTACK is the
 172    obstack to use (NULL for the default obstack).
 173
 174    This is the central point where equivalence processing can be
 175    turned on/off.  */
 176
 177 void
 178 value_range_equiv::equiv_add (const_tree var,
 179                               const value_range_equiv *var_vr,
 180                               bitmap_obstack *obstack)
 181 {
 182   if (!m_equiv)
 183     m_equiv = BITMAP_ALLOC (obstack);
 184   unsigned ver = SSA_NAME_VERSION (var);
 185   bitmap_set_bit (m_equiv, ver);
 186   if (var_vr && var_vr->m_equiv)
 187     bitmap_ior_into (m_equiv, var_vr->m_equiv);
 188 }
 189
 190 void
 191 value_range_equiv::intersect (const value_range_equiv *other)
 192 {
 193   if (dump_file && (dump_flags & TDF_DETAILS))
 194     {
 195       fprintf (dump_file, "Intersecting\n  ");
 196       dump_value_range (dump_file, this);
 197       fprintf (dump_file, "\nand\n  ");
 198       dump_value_range (dump_file, other);
 199       fprintf (dump_file, "\n");
 200     }
 201
 202   /* If THIS is varying we want to pick up equivalences from OTHER.
 203      Just special-case this here rather than trying to fixup after the
 204      fact.  */
 205   if (this->varying_p ())
 206     this->deep_copy (other);
 207   else
 208     {
 209       legacy_intersect (this, other);
 210       if (varying_p () || undefined_p ())
 211         equiv_clear ();
 212
 213       /* If the result is VR_UNDEFINED there is no need to mess with
 214          equivalencies.  */
 215       if (!undefined_p ())
 216         {
 217           /* The resulting set of equivalences for range intersection
 218              is the union of the two sets.  */
 219           if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
 220             bitmap_ior_into (m_equiv, other->m_equiv);
 221           else if (other->m_equiv && !m_equiv)
 222             {
 223               /* All equivalence bitmaps are allocated from the same
 224                  obstack.  So we can use the obstack associated with
 225                  VR to allocate this->m_equiv.  */
 226               m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
 227               bitmap_copy (m_equiv, other->m_equiv);
 228             }
 229         }
 230     }
 231
 232   if (dump_file && (dump_flags & TDF_DETAILS))
 233     {
 234       fprintf (dump_file, "to\n  ");
 235       dump_value_range (dump_file, this);
 236       fprintf (dump_file, "\n");
 237     }
 238 }
 239
 240 void
 241 value_range_equiv::union_ (const value_range_equiv *other)
 242 {
 243   if (dump_file && (dump_flags & TDF_DETAILS))
 244     {
 245       fprintf (dump_file, "Meeting\n  ");
 246       dump_value_range (dump_file, this);
 247       fprintf (dump_file, "\nand\n  ");
 248       dump_value_range (dump_file, other);
 249       fprintf (dump_file, "\n");
 250     }
 251
 252   /* If THIS is undefined we want to pick up equivalences from OTHER.
 253      Just special-case this here rather than trying to fixup after the fact.  */
 254   if (this->undefined_p ())
 255     this->deep_copy (other);
 256   else
 257     {
 258       legacy_union (this, other);
 259       if (varying_p () || undefined_p ())
 260         equiv_clear ();
 261
 262       /* The resulting set of equivalences is always the intersection of
 263          the two sets.  */
 264       if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv)
 265         bitmap_and_into (this->m_equiv, other->m_equiv);
 266       else if (this->m_equiv && !other->m_equiv)
 267         bitmap_clear (this->m_equiv);
 268     }
 269
 270   if (dump_file && (dump_flags & TDF_DETAILS))
 271     {
 272       fprintf (dump_file, "to\n  ");
 273       dump_value_range (dump_file, this);
 274       fprintf (dump_file, "\n");
 275     }
 276 }
 277
 278 void
 279 value_range_equiv::dump (FILE *file) const
 280 {
 281   value_range::dump (file);
 282   if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE)
 283       && m_equiv)
 284     {
 285       bitmap_iterator bi;
 286       unsigned i, c = 0;
 287
 288       fprintf (file, "  EQUIVALENCES: { ");
 289       EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi)
 290         {
 291           print_generic_expr (file, ssa_name (i));
 292           fprintf (file, " ");
 293           c++;
 294         }
 295       fprintf (file, "} (%u elements)", c);
 296     }
 297 }
 298
 299 void
 300 value_range_equiv::dump () const
 301 {
 302   dump (stderr);
 303 }
 304
 305 void
 306 dump_value_range (FILE *file, const value_range_equiv *vr)
 307 {
 308   if (!vr)
 309     fprintf (file, "[]");
 310   else
 311     vr->dump (file);
 312 }
 313
 314 DEBUG_FUNCTION void
 315 debug (const value_range_equiv *vr)
 316 {
 317   dump_value_range (stderr, vr);
 318 }
 319
 320 DEBUG_FUNCTION void
 321 debug (const value_range_equiv &vr)
 322 {
 323   dump_value_range (stderr, &vr);
 324 }