gcc/value-range-equiv.cc

/* Support routines for value ranges with equivalences.
   Copyright (C) 2020-2021 Free Software Foundation, Inc.

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 "gimple.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "value-range-equiv.h"

value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv,
				      value_range_kind kind)
{
  m_equiv = NULL;
  set (min, max, equiv, kind);
}

value_range_equiv::value_range_equiv (const value_range &other)
{
  m_equiv = NULL;
  set (other.min(), other.max (), NULL, other.kind ());
}

void
value_range_equiv::set (tree min, tree max, bitmap equiv,
			value_range_kind kind)
{
  value_range::set (min, max, kind);
  set_equiv (equiv);
  if (flag_checking)
    check ();
}

void
value_range_equiv::set (tree val)
{
  gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
  if (TREE_OVERFLOW_P (val))
    val = drop_tree_overflow (val);
  set (val, val);
}

void
value_range_equiv::set_undefined ()
{
  set (NULL, NULL, NULL, VR_UNDEFINED);
}

void
value_range_equiv::set_varying (tree type)
{
  value_range::set_varying (type);
  equiv_clear ();
}

/* Like set, but keep the equivalences in place.  */

void
value_range_equiv::update (tree min, tree max, value_range_kind kind)
{
  set (min, max,
       (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind);
}

/* Copy value_range in FROM into THIS while avoiding bitmap sharing.

   Note: The code that avoids the bitmap sharing looks at the existing
   this->m_equiv, so this function cannot be used to initalize an
   object.  Use the constructors for initialization.  */

void
value_range_equiv::deep_copy (const value_range_equiv *from)
{
  set (from->min (), from->max (), from->m_equiv, from->kind ());
}

void
value_range_equiv::move (value_range_equiv *from)
{
  set (from->min (), from->max (), NULL, from->kind ());
  m_equiv = from->m_equiv;
  from->m_equiv = NULL;
}

void
value_range_equiv::set_equiv (bitmap equiv)
{
  if (undefined_p () || varying_p ())
    equiv = NULL;
  /* Since updating the equivalence set involves deep copying the
     bitmaps, only do it if absolutely necessary.

     All equivalence bitmaps are allocated from the same obstack.  So
     we can use the obstack associated with EQUIV to allocate vr->equiv.  */
  if (m_equiv == NULL
      && equiv != NULL)
    m_equiv = BITMAP_ALLOC (equiv->obstack);

  if (equiv != m_equiv)
    {
      if (equiv && !bitmap_empty_p (equiv))
	bitmap_copy (m_equiv, equiv);
      else
	bitmap_clear (m_equiv);
    }
}

void
value_range_equiv::check ()
{
  value_range::verify_range ();
  switch (kind ())
    {
    case VR_UNDEFINED:
    case VR_VARYING:
      gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
    default:;
    }
}

/* Return true if the bitmaps B1 and B2 are equal.  */

static bool
vr_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
{
  return (b1 == b2
	  || ((!b1 || bitmap_empty_p (b1))
	      && (!b2 || bitmap_empty_p (b2)))
	  || (b1 && b2
	      && bitmap_equal_p (b1, b2)));
}

/* Returns TRUE if THIS == OTHER.  Ignores the equivalence bitmap if
   IGNORE_EQUIVS is TRUE.  */

bool
value_range_equiv::equal_p (const value_range_equiv &other,
			    bool ignore_equivs) const
{
  return (value_range::equal_p (other)
	  && (ignore_equivs || vr_bitmap_equal_p (m_equiv, other.m_equiv)));
}

void
value_range_equiv::equiv_clear ()
{
  if (m_equiv)
    bitmap_clear (m_equiv);
}

/* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence
   bitmap.  If no equivalence table has been created, OBSTACK is the
   obstack to use (NULL for the default obstack).

   This is the central point where equivalence processing can be
   turned on/off.  */

void
value_range_equiv::equiv_add (const_tree var,
			      const value_range_equiv *var_vr,
			      bitmap_obstack *obstack)
{
  if (!m_equiv)
    m_equiv = BITMAP_ALLOC (obstack);
  unsigned ver = SSA_NAME_VERSION (var);
  bitmap_set_bit (m_equiv, ver);
  if (var_vr && var_vr->m_equiv)
    bitmap_ior_into (m_equiv, var_vr->m_equiv);
}

void
value_range_equiv::intersect (const value_range_equiv *other)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "Intersecting\n  ");
      dump_value_range (dump_file, this);
      fprintf (dump_file, "\nand\n  ");
      dump_value_range (dump_file, other);
      fprintf (dump_file, "\n");
    }

  /* If THIS is varying we want to pick up equivalences from OTHER.
     Just special-case this here rather than trying to fixup after the
     fact.  */
  if (this->varying_p ())
    this->deep_copy (other);
  else
    {
      legacy_intersect (this, other);
      if (varying_p () || undefined_p ())
	equiv_clear ();

      /* If the result is VR_UNDEFINED there is no need to mess with
	 equivalencies.  */
      if (!undefined_p ())
	{
	  /* The resulting set of equivalences for range intersection
	     is the union of the two sets.  */
	  if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
	    bitmap_ior_into (m_equiv, other->m_equiv);
	  else if (other->m_equiv && !m_equiv)
	    {
	      /* All equivalence bitmaps are allocated from the same
		 obstack.  So we can use the obstack associated with
		 VR to allocate this->m_equiv.  */
	      m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
	      bitmap_copy (m_equiv, other->m_equiv);
	    }
	}
    }

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "to\n  ");
      dump_value_range (dump_file, this);
      fprintf (dump_file, "\n");
    }
}

void
value_range_equiv::union_ (const value_range_equiv *other)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "Meeting\n  ");
      dump_value_range (dump_file, this);
      fprintf (dump_file, "\nand\n  ");
      dump_value_range (dump_file, other);
      fprintf (dump_file, "\n");
    }

  /* If THIS is undefined we want to pick up equivalences from OTHER.
     Just special-case this here rather than trying to fixup after the fact.  */
  if (this->undefined_p ())
    this->deep_copy (other);
  else
    {
      legacy_union (this, other);
      if (varying_p () || undefined_p ())
	equiv_clear ();

      /* The resulting set of equivalences is always the intersection of
	 the two sets.  */
      if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv)
	bitmap_and_into (this->m_equiv, other->m_equiv);
      else if (this->m_equiv && !other->m_equiv)
	bitmap_clear (this->m_equiv);
    }

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "to\n  ");
      dump_value_range (dump_file, this);
      fprintf (dump_file, "\n");
    }
}

void
value_range_equiv::dump (FILE *file) const
{
  value_range::dump (file);
  if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE)
      && m_equiv)
    {
      bitmap_iterator bi;
      unsigned i, c = 0;

      fprintf (file, "  EQUIVALENCES: { ");
      EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi)
	{
	  print_generic_expr (file, ssa_name (i));
	  fprintf (file, " ");
	  c++;
	}
      fprintf (file, "} (%u elements)", c);
    }
}

void
value_range_equiv::dump () const
{
  dump (stderr);
}

void
dump_value_range (FILE *file, const value_range_equiv *vr)
{
  if (!vr)
    fprintf (file, "[]");
  else
    vr->dump (file);
}

DEBUG_FUNCTION void
debug (const value_range_equiv *vr)
{
  dump_value_range (stderr, vr);
}

DEBUG_FUNCTION void
debug (const value_range_equiv &vr)
{
  dump_value_range (stderr, &vr);
}