gcc/value-range-equiv.cc

   1 /* Support routines for value ranges with equivalences.
   2    Copyright (C) 2020 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->m_kind);
  94 }
  95
  96 void
  97 value_range_equiv::move (value_range_equiv *from)
  98 {
  99   set (from->min (), from->max (), NULL, from->m_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::check ();
 131   switch (m_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       value_range tem = intersect_helper (this, other);
 210       this->update (tem.min (), tem.max (), tem.kind ());
 211
 212       /* If the result is VR_UNDEFINED there is no need to mess with
 213          equivalencies.  */
 214       if (!undefined_p ())
 215         {
 216           /* The resulting set of equivalences for range intersection
 217              is the union of the two sets.  */
 218           if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
 219             bitmap_ior_into (m_equiv, other->m_equiv);
 220           else if (other->m_equiv && !m_equiv)
 221             {
 222               /* All equivalence bitmaps are allocated from the same
 223                  obstack.  So we can use the obstack associated with
 224                  VR to allocate this->m_equiv.  */
 225               m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
 226               bitmap_copy (m_equiv, other->m_equiv);
 227             }
 228         }
 229     }
 230
 231   if (dump_file && (dump_flags & TDF_DETAILS))
 232     {
 233       fprintf (dump_file, "to\n  ");
 234       dump_value_range (dump_file, this);
 235       fprintf (dump_file, "\n");
 236     }
 237 }
 238
 239 void
 240 value_range_equiv::union_ (const value_range_equiv *other)
 241 {
 242   if (dump_file && (dump_flags & TDF_DETAILS))
 243     {
 244       fprintf (dump_file, "Meeting\n  ");
 245       dump_value_range (dump_file, this);
 246       fprintf (dump_file, "\nand\n  ");
 247       dump_value_range (dump_file, other);
 248       fprintf (dump_file, "\n");
 249     }
 250
 251   /* If THIS is undefined we want to pick up equivalences from OTHER.
 252      Just special-case this here rather than trying to fixup after the fact.  */
 253   if (this->undefined_p ())
 254     this->deep_copy (other);
 255   else
 256     {
 257       value_range tem = union_helper (this, other);
 258       this->update (tem.min (), tem.max (), tem.kind ());
 259
 260       /* The resulting set of equivalences is always the intersection of
 261          the two sets.  */
 262       if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv)
 263         bitmap_and_into (this->m_equiv, other->m_equiv);
 264       else if (this->m_equiv && !other->m_equiv)
 265         bitmap_clear (this->m_equiv);
 266     }
 267
 268   if (dump_file && (dump_flags & TDF_DETAILS))
 269     {
 270       fprintf (dump_file, "to\n  ");
 271       dump_value_range (dump_file, this);
 272       fprintf (dump_file, "\n");
 273     }
 274 }
 275
 276 void
 277 value_range_equiv::dump (FILE *file) const
 278 {
 279   value_range::dump (file);
 280   if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
 281       && m_equiv)
 282     {
 283       bitmap_iterator bi;
 284       unsigned i, c = 0;
 285
 286       fprintf (file, "  EQUIVALENCES: { ");
 287       EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi)
 288         {
 289           print_generic_expr (file, ssa_name (i));
 290           fprintf (file, " ");
 291           c++;
 292         }
 293       fprintf (file, "} (%u elements)", c);
 294     }
 295 }
 296
 297 void
 298 value_range_equiv::dump () const
 299 {
 300   dump (stderr);
 301 }
 302
 303 void
 304 dump_value_range (FILE *file, const value_range_equiv *vr)
 305 {
 306   if (!vr)
 307     fprintf (file, "[]");
 308   else
 309     vr->dump (file);
 310 }
 311
 312 DEBUG_FUNCTION void
 313 debug (const value_range_equiv *vr)
 314 {
 315   dump_value_range (stderr, vr);
 316 }
 317
 318 DEBUG_FUNCTION void
 319 debug (const value_range_equiv &vr)
 320 {
 321   dump_value_range (stderr, &vr);
 322 }