xref: /netbsd/external/gpl3/gcc/dist/gcc/gimple-range-gori.cc (revision f0fbc68b)

/* Gimple range GORI functions.
   Copyright (C) 2017-2022 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod <amacleod@redhat.com>
   and Aldy Hernandez <aldyh@redhat.com>.

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

// Calculate what we can determine of the range of this unary
// statement's operand if the lhs of the expression has the range
// LHS_RANGE.  Return false if nothing can be determined.

bool
gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range)
{
  gcc_checking_assert (gimple_num_ops (stmt) < 3);
  // Give up on empty ranges.
  if (lhs_range.undefined_p ())
    return false;

  // Unary operations require the type of the first operand in the
  // second range position.
  tree type = TREE_TYPE (gimple_range_operand1 (stmt));
  int_range<2> type_range (type);
  return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
						 type_range);
}

// Calculate what we can determine of the range of this statement's
// first operand if the lhs of the expression has the range LHS_RANGE
// and the second operand has the range OP2_RANGE.  Return false if
// nothing can be determined.

bool
gimple_range_calc_op1 (irange &r, const gimple *stmt,
		       const irange &lhs_range, const irange &op2_range)
{
  // Give up on empty ranges.
  if (lhs_range.undefined_p ())
    return false;

  // Unary operation are allowed to pass a range in for second operand
  // as there are often additional restrictions beyond the type which
  // can be imposed.  See operator_cast::op1_range().
  tree type = TREE_TYPE (gimple_range_operand1 (stmt));
  // If op2 is undefined, solve as if it is varying.
  if (op2_range.undefined_p ())
    {
      // This is sometimes invoked on single operand stmts.
      if (gimple_num_ops (stmt) < 3)
	return false;
      int_range<2> trange (TREE_TYPE (gimple_range_operand2 (stmt)));
      return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
						     trange);
    }
  return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
						 op2_range);
}

// Calculate what we can determine of the range of this statement's
// second operand if the lhs of the expression has the range LHS_RANGE
// and the first operand has the range OP1_RANGE.  Return false if
// nothing can be determined.

bool
gimple_range_calc_op2 (irange &r, const gimple *stmt,
		       const irange &lhs_range, const irange &op1_range)
{
  // Give up on empty ranges.
  if (lhs_range.undefined_p ())
    return false;

  tree type = TREE_TYPE (gimple_range_operand2 (stmt));
  // If op1 is undefined, solve as if it is varying.
  if (op1_range.undefined_p ())
    {
      int_range<2> trange (TREE_TYPE (gimple_range_operand1 (stmt)));
      return gimple_range_handler (stmt)->op2_range (r, type, lhs_range,
						     trange);
    }
  return gimple_range_handler (stmt)->op2_range (r, type, lhs_range,
						 op1_range);
}

// Return TRUE if GS is a logical && or || expression.

static inline bool
is_gimple_logical_p (const gimple *gs)
{
  // Look for boolean and/or condition.
  if (is_gimple_assign (gs))
    switch (gimple_expr_code (gs))
      {
	case TRUTH_AND_EXPR:
	case TRUTH_OR_EXPR:
	  return true;

	case BIT_AND_EXPR:
	case BIT_IOR_EXPR:
	  // Bitwise operations on single bits are logical too.
	  if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
				  boolean_type_node))
	    return true;
	  break;

	default:
	  break;
      }
  return false;
}

/* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
   have range information calculated for them, and what the
   dependencies on each other are.

   Information for a basic block is calculated once and stored.  It is
   only calculated the first time a query is made, so if no queries
   are made, there is little overhead.

   The def_chain bitmap is indexed by SSA_NAME_VERSION.  Bits are set
   within this bitmap to indicate SSA names that are defined in the
   SAME block and used to calculate this SSA name.


    <bb 2> :
      _1 = x_4(D) + -2;
      _2 = _1 * 4;
      j_7 = foo ();
      q_5 = _2 + 3;
      if (q_5 <= 13)

    _1  : x_4(D)
    _2  : 1  x_4(D)
    q_5  : _1  _2  x_4(D)

    This dump indicates the bits set in the def_chain vector.
    as well as demonstrates the def_chain bits for the related ssa_names.

    Checking the chain for _2 indicates that _1 and x_4 are used in
    its evaluation.

    Def chains also only include statements which are valid gimple
    so a def chain will only span statements for which the range
    engine implements operations for.  */


// Construct a range_def_chain.

range_def_chain::range_def_chain ()
{
  bitmap_obstack_initialize (&m_bitmaps);
  m_def_chain.create (0);
  m_def_chain.safe_grow_cleared (num_ssa_names);
  m_logical_depth = 0;
}

// Destruct a range_def_chain.

range_def_chain::~range_def_chain ()
{
  m_def_chain.release ();
  bitmap_obstack_release (&m_bitmaps);
}

// Return true if NAME is in the def chain of DEF.  If BB is provided,
// only return true if the defining statement of DEF is in BB.

bool
range_def_chain::in_chain_p (tree name, tree def)
{
  gcc_checking_assert (gimple_range_ssa_p (def));
  gcc_checking_assert (gimple_range_ssa_p (name));

  // Get the defintion chain for DEF.
  bitmap chain = get_def_chain (def);

  if (chain == NULL)
    return false;
  return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
}

// Add either IMP or the import list B to the import set of DATA.

void
range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
{
  // If there are no imports, just return
  if (imp == NULL_TREE && !b)
    return;
  if (!data.m_import)
    data.m_import = BITMAP_ALLOC (&m_bitmaps);
  if (imp != NULL_TREE)
    bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
  else
    bitmap_ior_into (data.m_import, b);
}

// Return the import list for NAME.

bitmap
range_def_chain::get_imports (tree name)
{
  if (!has_def_chain (name))
    get_def_chain (name);
  bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
  return i;
}

// Return true if IMPORT is an import to NAMEs def chain.

bool
range_def_chain::chain_import_p (tree name, tree import)
{
  bitmap b = get_imports (name);
  if (b)
    return bitmap_bit_p (b, SSA_NAME_VERSION (import));
  return false;
}

// Build def_chains for NAME if it is in BB.  Copy the def chain into RESULT.

void
range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
{
  if (!gimple_range_ssa_p (dep))
    return;

  unsigned v = SSA_NAME_VERSION (name);
  if (v >= m_def_chain.length ())
    m_def_chain.safe_grow_cleared (num_ssa_names + 1);
  struct rdc &src = m_def_chain[v];
  gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
  unsigned dep_v = SSA_NAME_VERSION (dep);
  bitmap b;

  // Set the direct dependency cache entries.
  if (!src.ssa1)
    src.ssa1 = dep;
  else if (!src.ssa2 && src.ssa1 != dep)
    src.ssa2 = dep;

  // Don't calculate imports or export/dep chains if BB is not provided.
  // This is usually the case for when the temporal cache wants the direct
  // dependencies of a stmt.
  if (!bb)
    return;

  if (!src.bm)
    src.bm = BITMAP_ALLOC (&m_bitmaps);

  // Add this operand into the result.
  bitmap_set_bit (src.bm, dep_v);

  if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
    {
      // Get the def chain for the operand.
      b = get_def_chain (dep);
      // If there was one, copy it into result.  Access def_chain directly
      // as the get_def_chain request above could reallocate the vector.
      if (b)
	bitmap_ior_into (m_def_chain[v].bm, b);
      // And copy the import list.
      set_import (m_def_chain[v], NULL_TREE, get_imports (dep));
    }
  else
    // Originated outside the block, so it is an import.
    set_import (src, dep, NULL);
}

bool
range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
{
  bitmap a = get_def_chain (name);
  if (a && b)
    return bitmap_intersect_p (a, b);
  return false;
}

void
range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
{
  bitmap r = get_def_chain (name);
  if (r)
    bitmap_ior_into (b, r);
}


// Return TRUE if NAME has been processed for a def_chain.

inline bool
range_def_chain::has_def_chain (tree name)
{
  // Ensure there is an entry in the internal vector.
  unsigned v = SSA_NAME_VERSION (name);
  if (v >= m_def_chain.length ())
    m_def_chain.safe_grow_cleared (num_ssa_names + 1);
  return (m_def_chain[v].ssa1 != 0);
}



// Calculate the def chain for NAME and all of its dependent
// operands. Only using names in the same BB.  Return the bitmap of
// all names in the m_def_chain.  This only works for supported range
// statements.

bitmap
range_def_chain::get_def_chain (tree name)
{
  tree ssa1, ssa2, ssa3;
  unsigned v = SSA_NAME_VERSION (name);

  // If it has already been processed, just return the cached value.
  if (has_def_chain (name) && m_def_chain[v].bm)
    return m_def_chain[v].bm;

  // No definition chain for default defs.
  if (SSA_NAME_IS_DEFAULT_DEF (name))
    {
      // A Default def is always an import.
      set_import (m_def_chain[v], name, NULL);
      return NULL;
    }

  gimple *stmt = SSA_NAME_DEF_STMT (name);
  if (gimple_range_handler (stmt))
    {
      ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
      ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
      ssa3 = NULL_TREE;
    }
  else if (is_a<gassign *> (stmt)
	   && gimple_assign_rhs_code (stmt) == COND_EXPR)
    {
      gassign *st = as_a<gassign *> (stmt);
      ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st));
      ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st));
      ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st));
    }
  else
    {
      // Stmts not understood are always imports.
      set_import (m_def_chain[v], name, NULL);
      return NULL;
    }

  // Terminate the def chains if we see too many cascading stmts.
  if (m_logical_depth == param_ranger_logical_depth)
    return NULL;

  // Increase the depth if we have a pair of ssa-names.
  if (ssa1 && ssa2)
    m_logical_depth++;

  register_dependency (name, ssa1, gimple_bb (stmt));
  register_dependency (name, ssa2, gimple_bb (stmt));
  register_dependency (name, ssa3, gimple_bb (stmt));
  // Stmts with no understandable operands are also imports.
  if (!ssa1 && !ssa2 & !ssa3)
    set_import (m_def_chain[v], name, NULL);

  if (ssa1 && ssa2)
    m_logical_depth--;

  return m_def_chain[v].bm;
}

// Dump what we know for basic block BB to file F.

void
range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
{
  unsigned x, y;
  bitmap_iterator bi;

  // Dump the def chain for each SSA_NAME defined in BB.
  for (x = 1; x < num_ssa_names; x++)
    {
      tree name = ssa_name (x);
      if (!name)
	continue;
      gimple *stmt = SSA_NAME_DEF_STMT (name);
      if (!stmt || (bb && gimple_bb (stmt) != bb))
	continue;
      bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
      if (chain && !bitmap_empty_p (chain))
	{
	  fprintf (f, prefix);
	  print_generic_expr (f, name, TDF_SLIM);
	  fprintf (f, " : ");

	  bitmap imports = get_imports (name);
	  EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
	    {
	      print_generic_expr (f, ssa_name (y), TDF_SLIM);
	      if (imports && bitmap_bit_p (imports, y))
		fprintf (f, "(I)");
	      fprintf (f, "  ");
	    }
	  fprintf (f, "\n");
	}
    }
}


// -------------------------------------------------------------------

/* GORI_MAP is used to accumulate what SSA names in a block can
   generate range information, and provides tools for the block ranger
   to enable it to efficiently calculate these ranges.

   GORI stands for "Generates Outgoing Range Information."

   It utilizes the range_def_chain class to contruct def_chains.
   Information for a basic block is calculated once and stored.  It is
   only calculated the first time a query is made.  If no queries are
   made, there is little overhead.

   one bitmap is maintained for each basic block:
   m_outgoing  : a set bit indicates a range can be generated for a name.

   Generally speaking, the m_outgoing vector is the union of the
   entire def_chain of all SSA names used in the last statement of the
   block which generate ranges.  */


// Initialize a gori-map structure.

gori_map::gori_map ()
{
  m_outgoing.create (0);
  m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
  m_incoming.create (0);
  m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
  m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
}

// Free any memory the GORI map allocated.

gori_map::~gori_map ()
{
  m_incoming.release ();
  m_outgoing.release ();
}

// Return the bitmap vector of all export from BB.  Calculate if necessary.

bitmap
gori_map::exports (basic_block bb)
{
  if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
    calculate_gori (bb);
  return m_outgoing[bb->index];
}

// Return the bitmap vector of all imports to BB.  Calculate if necessary.

bitmap
gori_map::imports (basic_block bb)
{
  if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
    calculate_gori (bb);
  return m_incoming[bb->index];
}

// Return true if NAME is can have ranges generated for it from basic
// block BB.

bool
gori_map::is_export_p (tree name, basic_block bb)
{
  // If no BB is specified, test if it is exported anywhere in the IL.
  if (!bb)
    return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
  return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
}

// Clear the m_maybe_variant bit so ranges will not be tracked for NAME.

void
gori_map::set_range_invariant (tree name)
{
  bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
}

// Return true if NAME is an import to block BB.

bool
gori_map::is_import_p (tree name, basic_block bb)
{
  // If no BB is specified, test if it is exported anywhere in the IL.
  return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
}

// If NAME is non-NULL and defined in block BB, calculate the def
// chain and add it to m_outgoing.

void
gori_map::maybe_add_gori (tree name, basic_block bb)
{
  if (name)
    {
      // Check if there is a def chain, regardless of the block.
      add_def_chain_to_bitmap (m_outgoing[bb->index], name);
      // Check for any imports.
      bitmap imp = get_imports (name);
      // If there were imports, add them so we can recompute
      if (imp)
	bitmap_ior_into (m_incoming[bb->index], imp);
      // This name is always an import.
      if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
	bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));

      // Def chain doesn't include itself, and even if there isn't a
      // def chain, this name should be added to exports.
      bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
    }
}

// Calculate all the required information for BB.

void
gori_map::calculate_gori (basic_block bb)
{
  tree name;
  if (bb->index >= (signed int)m_outgoing.length ())
    {
      m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
      m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
    }
  gcc_checking_assert (m_outgoing[bb->index] == NULL);
  m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
  m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);

  if (single_succ_p (bb))
    return;

  // If this block's last statement may generate range informaiton, go
  // calculate it.
  gimple *stmt = gimple_outgoing_range_stmt_p (bb);
  if (!stmt)
    return;
  if (is_a<gcond *> (stmt))
    {
      gcond *gc = as_a<gcond *>(stmt);
      name = gimple_range_ssa_p (gimple_cond_lhs (gc));
      maybe_add_gori (name, gimple_bb (stmt));

      name = gimple_range_ssa_p (gimple_cond_rhs (gc));
      maybe_add_gori (name, gimple_bb (stmt));
    }
  else
    {
      // Do not process switches if they are too large.
      if (EDGE_COUNT (bb->succs) > (unsigned)param_evrp_switch_limit)
	return;
      gswitch *gs = as_a<gswitch *>(stmt);
      name = gimple_range_ssa_p (gimple_switch_index (gs));
      maybe_add_gori (name, gimple_bb (stmt));
    }
  // Add this bitmap to the aggregate list of all outgoing names.
  bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
}

// Dump the table information for BB to file F.

void
gori_map::dump (FILE *f, basic_block bb, bool verbose)
{
  // BB was not processed.
  if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
    return;

  tree name;

  bitmap imp = imports (bb);
  if (!bitmap_empty_p (imp))
    {
      if (verbose)
	fprintf (f, "bb<%u> Imports: ",bb->index);
      else
	fprintf (f, "Imports: ");
      FOR_EACH_GORI_IMPORT_NAME (*this, bb, name)
	{
	  print_generic_expr (f, name, TDF_SLIM);
	  fprintf (f, "  ");
	}
      fputc ('\n', f);
    }

  if (verbose)
    fprintf (f, "bb<%u> Exports: ",bb->index);
  else
    fprintf (f, "Exports: ");
  // Dump the export vector.
  FOR_EACH_GORI_EXPORT_NAME (*this, bb, name)
    {
      print_generic_expr (f, name, TDF_SLIM);
      fprintf (f, "  ");
    }
  fputc ('\n', f);

  range_def_chain::dump (f, bb, "         ");
}

// Dump the entire GORI map structure to file F.

void
gori_map::dump (FILE *f)
{
  basic_block bb;
  FOR_EACH_BB_FN (bb, cfun)
    dump (f, bb);
}

DEBUG_FUNCTION void
debug (gori_map &g)
{
  g.dump (stderr);
}

// -------------------------------------------------------------------

// Construct a gori_compute object.

gori_compute::gori_compute (int not_executable_flag)
		      : outgoing (param_evrp_switch_limit), tracer ("GORI ")
{
  m_not_executable_flag = not_executable_flag;
  // Create a boolean_type true and false range.
  m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node);
  m_bool_one = int_range<2> (boolean_true_node, boolean_true_node);
  if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI))
    tracer.enable_trace ();
}

// Given the switch S, return an evaluation in R for NAME when the lhs
// evaluates to LHS.  Returning false means the name being looked for
// was not resolvable.

bool
gori_compute::compute_operand_range_switch (irange &r, gswitch *s,
					    const irange &lhs,
					    tree name, fur_source &src)
{
  tree op1 = gimple_switch_index (s);

  // If name matches, the range is simply the range from the edge.
  // Empty ranges are viral as they are on a path which isn't
  // executable.
  if (op1 == name || lhs.undefined_p ())
    {
      r = lhs;
      return true;
    }

  // If op1 is in the defintion chain, pass lhs back.
  if (gimple_range_ssa_p (op1) && in_chain_p (name, op1))
    return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);

  return false;
}


// Return an evaluation for NAME as it would appear in STMT when the
// statement's lhs evaluates to LHS.  If successful, return TRUE and
// store the evaluation in R, otherwise return FALSE.

bool
gori_compute::compute_operand_range (irange &r, gimple *stmt,
				     const irange &lhs, tree name,
				     fur_source &src)
{
  // If the lhs doesn't tell us anything, neither will unwinding further.
  if (lhs.varying_p ())
    return false;

  // Empty ranges are viral as they are on an unexecutable path.
  if (lhs.undefined_p ())
    {
      r.set_undefined ();
      return true;
    }
  if (is_a<gswitch *> (stmt))
    return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name,
					 src);
  if (!gimple_range_handler (stmt))
    return false;

  tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
  tree op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));

  // Handle end of lookup first.
  if (op1 == name)
    return compute_operand1_range (r, stmt, lhs, name, src);
  if (op2 == name)
    return compute_operand2_range (r, stmt, lhs, name, src);

  // NAME is not in this stmt, but one of the names in it ought to be
  // derived from it.
  bool op1_in_chain = op1 && in_chain_p (name, op1);
  bool op2_in_chain = op2 && in_chain_p (name, op2);

  // If neither operand is derived, then this stmt tells us nothing.
  if (!op1_in_chain && !op2_in_chain)
    return false;

  bool res;
  // Process logicals as they have special handling.
  if (is_gimple_logical_p (stmt))
    {
      unsigned idx;
      if ((idx = tracer.header ("compute_operand ")))
	{
	  print_generic_expr (dump_file, name, TDF_SLIM);
	  fprintf (dump_file, " with LHS = ");
	  lhs.dump (dump_file);
	  fprintf (dump_file, " at stmt ");
	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	}

      int_range_max op1_trange, op1_frange;
      int_range_max op2_trange, op2_frange;
      compute_logical_operands (op1_trange, op1_frange, stmt, lhs,
				name, src, op1, op1_in_chain);
      compute_logical_operands (op2_trange, op2_frange, stmt, lhs,
				name, src, op2, op2_in_chain);
      res = logical_combine (r, gimple_expr_code (stmt), lhs,
			     op1_trange, op1_frange, op2_trange, op2_frange);
      if (idx)
	tracer.trailer (idx, "compute_operand", res, name, r);
    }
  // Follow the appropriate operands now.
  else if (op1_in_chain && op2_in_chain)
    res = compute_operand1_and_operand2_range (r, stmt, lhs, name, src);
  else if (op1_in_chain)
    res = compute_operand1_range (r, stmt, lhs, name, src);
  else if (op2_in_chain)
    res = compute_operand2_range (r, stmt, lhs, name, src);
  else
    gcc_unreachable ();

  // If neither operand is derived, this statement tells us nothing.
  return res;
}


// Return TRUE if range R is either a true or false compatible range.

static bool
range_is_either_true_or_false (const irange &r)
{
  if (r.undefined_p ())
    return false;

  // This is complicated by the fact that Ada has multi-bit booleans,
  // so true can be ~[0, 0] (i.e. [1,MAX]).
  tree type = r.type ();
  gcc_checking_assert (range_compatible_p (type, boolean_type_node));
  return (r.singleton_p () || !r.contains_p (build_zero_cst (type)));
}

// Evaluate a binary logical expression by combining the true and
// false ranges for each of the operands based on the result value in
// the LHS.

bool
gori_compute::logical_combine (irange &r, enum tree_code code,
			       const irange &lhs,
			       const irange &op1_true, const irange &op1_false,
			       const irange &op2_true, const irange &op2_false)
{
  if (op1_true.varying_p () && op1_false.varying_p ()
      && op2_true.varying_p () && op2_false.varying_p ())
    return false;

  unsigned idx;
  if ((idx = tracer.header ("logical_combine")))
    {
      switch (code)
        {
	  case TRUTH_OR_EXPR:
	  case BIT_IOR_EXPR:
	    fprintf (dump_file, " || ");
	    break;
	  case TRUTH_AND_EXPR:
	  case BIT_AND_EXPR:
	    fprintf (dump_file, " && ");
	    break;
	  default:
	    break;
	}
      fprintf (dump_file, " with LHS = ");
      lhs.dump (dump_file);
      fputc ('\n', dump_file);

      tracer.print (idx, "op1_true = ");
      op1_true.dump (dump_file);
      fprintf (dump_file, "  op1_false = ");
      op1_false.dump (dump_file);
      fputc ('\n', dump_file);
      tracer.print (idx, "op2_true = ");
      op2_true.dump (dump_file);
      fprintf (dump_file, "  op2_false = ");
      op2_false.dump (dump_file);
      fputc ('\n', dump_file);
    }

  // This is not a simple fold of a logical expression, rather it
  // determines ranges which flow through the logical expression.
  //
  // Assuming x_8 is an unsigned char, and relational statements:
  //	      b_1 = x_8 < 20
  //	      b_2 = x_8 > 5
  // consider the logical expression and branch:
  //          c_2 = b_1 && b_2
  //          if (c_2)
  //
  // To determine the range of x_8 on either edge of the branch, one
  // must first determine what the range of x_8 is when the boolean
  // values of b_1 and b_2 are both true and false.
  //    b_1 TRUE      x_8 = [0, 19]
  //    b_1 FALSE     x_8 = [20, 255]
  //    b_2 TRUE      x_8 = [6, 255]
  //    b_2 FALSE     x_8 = [0,5].
  //
  // These ranges are then combined based on the expected outcome of
  // the branch.  The range on the TRUE side of the branch must satisfy
  //     b_1 == true && b_2 == true
  //
  // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
  // must be true.  The range of x_8 on the true side must be the
  // intersection of both ranges since both must be true.  Thus the
  // range of x_8 on the true side is [6, 19].
  //
  // To determine the ranges on the FALSE side, all 3 combinations of
  // failing ranges must be considered, and combined as any of them
  // can cause the false result.
  //
  // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
  // FALSE results and combine them.  If we fell back to VARYING any
  // range restrictions that have been discovered up to this point
  // would be lost.
  if (!range_is_either_true_or_false (lhs))
    {
      bool res;
      int_range_max r1;
      if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false,
			   op2_true, op2_false)
	  && logical_combine (r, code, m_bool_one, op1_true, op1_false,
			      op2_true, op2_false))
	{
	  r.union_ (r1);
	  res = true;
	}
      else
	res = false;
      if (idx)
	tracer.trailer (idx, "logical_combine", res, NULL_TREE, r);
    }

  switch (code)
    {
      //  A logical AND combines ranges from 2 boolean conditions.
      //       c_2 = b_1 && b_2
      case TRUTH_AND_EXPR:
      case BIT_AND_EXPR:
        if (!lhs.zero_p ())
	  {
	    // The TRUE side is the intersection of the 2 true ranges.
	    r = op1_true;
	    r.intersect (op2_true);
	  }
	else
	  {
	    // The FALSE side is the union of the other 3 cases.
	    int_range_max ff (op1_false);
	    ff.intersect (op2_false);
	    int_range_max tf (op1_true);
	    tf.intersect (op2_false);
	    int_range_max ft (op1_false);
	    ft.intersect (op2_true);
	    r = ff;
	    r.union_ (tf);
	    r.union_ (ft);
	  }
        break;
      //  A logical OR combines ranges from 2 boolean conditons.
      // 	c_2 = b_1 || b_2
      case TRUTH_OR_EXPR:
      case BIT_IOR_EXPR:
        if (lhs.zero_p ())
	  {
	    // An OR operation will only take the FALSE path if both
	    // operands are false simlulateously, which means they should
	    // be intersected.  !(x || y) == !x && !y
	    r = op1_false;
	    r.intersect (op2_false);
	  }
	else
	  {
	    // The TRUE side of an OR operation will be the union of
	    // the other three combinations.
	    int_range_max tt (op1_true);
	    tt.intersect (op2_true);
	    int_range_max tf (op1_true);
	    tf.intersect (op2_false);
	    int_range_max ft (op1_false);
	    ft.intersect (op2_true);
	    r = tt;
	    r.union_ (tf);
	    r.union_ (ft);
	  }
	break;
      default:
        gcc_unreachable ();
    }

  if (idx)
    tracer.trailer (idx, "logical_combine", true, NULL_TREE, r);
  return true;
}


// Given a logical STMT, calculate true and false ranges for each
// potential path of NAME, assuming NAME came through the OP chain if
// OP_IN_CHAIN is true.

void
gori_compute::compute_logical_operands (irange &true_range, irange &false_range,
					gimple *stmt,
					const irange &lhs,
					tree name, fur_source &src,
					tree op, bool op_in_chain)
{
  gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL;
  if (!op_in_chain || !src_stmt || chain_import_p (gimple_get_lhs (stmt), op))
    {
      // If op is not in the def chain, or defined in this block,
      // use its known value on entry to the block.
      src.get_operand (true_range, name);
      false_range = true_range;
      unsigned idx;
      if ((idx = tracer.header ("logical_operand")))
	{
	  print_generic_expr (dump_file, op, TDF_SLIM);
	  fprintf (dump_file, " not in computation chain. Queried.\n");
	  tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range);
        }
      return;
    }

  enum tree_code code = gimple_expr_code (stmt);
  // Optimize [0 = x | y], since neither operand can ever be non-zero.
  if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
    {
      if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name,
				  src))
	src.get_operand (false_range, name);
      true_range = false_range;
      return;
    }

  // Optimize [1 = x & y], since neither operand can ever be zero.
  if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
    {
      if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
	src.get_operand (true_range, name);
      false_range = true_range;
      return;
    }

  // Calculate ranges for true and false on both sides, since the false
  // path is not always a simple inversion of the true side.
  if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
    src.get_operand (true_range, name);
  if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src))
    src.get_operand (false_range, name);
}

// Calculate a range for NAME from the operand 1 position of STMT
// assuming the result of the statement is LHS.  Return the range in
// R, or false if no range could be calculated.

bool
gori_compute::compute_operand1_range (irange &r, gimple *stmt,
				      const irange &lhs, tree name,
				      fur_source &src)
{
  int_range_max op1_range, op2_range;
  tree op1 = gimple_range_operand1 (stmt);
  tree op2 = gimple_range_operand2 (stmt);

  // Fetch the known range for op1 in this block.
  src.get_operand (op1_range, op1);

  // Now range-op calcuate and put that result in r.
  if (op2)
    {
      src.get_operand (op2_range, op2);
      if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range))
	return false;
    }
  else
    {
      // We pass op1_range to the unary operation.  Nomally it's a
      // hidden range_for_type parameter, but sometimes having the
      // actual range can result in better information.
      if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range))
	return false;
    }

  unsigned idx;
  if ((idx = tracer.header ("compute op 1 (")))
    {
      print_generic_expr (dump_file, op1, TDF_SLIM);
      fprintf (dump_file, ") at ");
      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
      tracer.print (idx, "LHS =");
      lhs.dump (dump_file);
      if (op2 && TREE_CODE (op2) == SSA_NAME)
	{
	  fprintf (dump_file, ", ");
	  print_generic_expr (dump_file, op2, TDF_SLIM);
	  fprintf (dump_file, " = ");
	  op2_range.dump (dump_file);
	}
      fprintf (dump_file, "\n");
      tracer.print (idx, "Computes ");
      print_generic_expr (dump_file, op1, TDF_SLIM);
      fprintf (dump_file, " = ");
      r.dump (dump_file);
      fprintf (dump_file, " intersect Known range : ");
      op1_range.dump (dump_file);
      fputc ('\n', dump_file);
    }
  // Intersect the calculated result with the known result and return if done.
  if (op1 == name)
    {
      r.intersect (op1_range);
      if (idx)
	tracer.trailer (idx, "produces ", true, name, r);
      return true;
    }
  // If the calculation continues, we're using op1_range as the new LHS.
  op1_range.intersect (r);

  if (idx)
    tracer.trailer (idx, "produces ", true, op1, op1_range);
  gimple *src_stmt = SSA_NAME_DEF_STMT (op1);
  gcc_checking_assert (src_stmt);

  // Then feed this range back as the LHS of the defining statement.
  return compute_operand_range (r, src_stmt, op1_range, name, src);
}


// Calculate a range for NAME from the operand 2 position of S
// assuming the result of the statement is LHS.  Return the range in
// R, or false if no range could be calculated.

bool
gori_compute::compute_operand2_range (irange &r, gimple *stmt,
				      const irange &lhs, tree name,
				      fur_source &src)
{
  int_range_max op1_range, op2_range;
  tree op1 = gimple_range_operand1 (stmt);
  tree op2 = gimple_range_operand2 (stmt);

  src.get_operand (op1_range, op1);
  src.get_operand (op2_range, op2);

  // Intersect with range for op2 based on lhs and op1.
  if (!gimple_range_calc_op2 (r, stmt, lhs, op1_range))
    return false;

  unsigned idx;
  if ((idx = tracer.header ("compute op 2 (")))
    {
      print_generic_expr (dump_file, op2, TDF_SLIM);
      fprintf (dump_file, ") at ");
      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
      tracer.print (idx, "LHS = ");
      lhs.dump (dump_file);
      if (TREE_CODE (op1) == SSA_NAME)
	{
	  fprintf (dump_file, ", ");
	  print_generic_expr (dump_file, op1, TDF_SLIM);
	  fprintf (dump_file, " = ");
	  op1_range.dump (dump_file);
	}
      fprintf (dump_file, "\n");
      tracer.print (idx, "Computes ");
      print_generic_expr (dump_file, op2, TDF_SLIM);
      fprintf (dump_file, " = ");
      r.dump (dump_file);
      fprintf (dump_file, " intersect Known range : ");
      op2_range.dump (dump_file);
      fputc ('\n', dump_file);
    }
  // Intersect the calculated result with the known result and return if done.
  if (op2 == name)
    {
      r.intersect (op2_range);
      if (idx)
	tracer.trailer (idx, " produces ", true, NULL_TREE, r);
      return true;
    }
  // If the calculation continues, we're using op2_range as the new LHS.
  op2_range.intersect (r);

  if (idx)
    tracer.trailer (idx, " produces ", true, op2, op2_range);
  gimple *src_stmt = SSA_NAME_DEF_STMT (op2);
  gcc_checking_assert (src_stmt);
//  gcc_checking_assert (!is_import_p (op2, find.bb));

  // Then feed this range back as the LHS of the defining statement.
  return compute_operand_range (r, src_stmt, op2_range, name, src);
}

// Calculate a range for NAME from both operand positions of S
// assuming the result of the statement is LHS.  Return the range in
// R, or false if no range could be calculated.

bool
gori_compute::compute_operand1_and_operand2_range (irange &r,
						   gimple *stmt,
						   const irange &lhs,
						   tree name,
						   fur_source &src)
{
  int_range_max op_range;

  // Calculate a good a range for op2.  Since op1 == op2, this will
  // have already included whatever the actual range of name is.
  if (!compute_operand2_range (op_range, stmt, lhs, name, src))
    return false;

  // Now get the range thru op1.
  if (!compute_operand1_range (r, stmt, lhs, name, src))
    return false;

  // Both operands have to be simultaneously true, so perform an intersection.
  r.intersect (op_range);
  return true;
}

// Return TRUE if NAME can be recomputed on any edge exiting BB.  If any
// direct dependant is exported, it may also change the computed value of NAME.

bool
gori_compute::may_recompute_p (tree name, basic_block bb)
{
  tree dep1 = depend1 (name);
  tree dep2 = depend2 (name);

  // If the first dependency is not set, there is no recompuation.
  if (!dep1)
    return false;

  // Don't recalculate PHIs or statements with side_effects.
  gimple *s = SSA_NAME_DEF_STMT (name);
  if (is_a<gphi *> (s) || gimple_has_side_effects (s))
    return false;

  // If edge is specified, check if NAME can be recalculated on that edge.
  if (bb)
    return ((is_export_p (dep1, bb))
	    || (dep2 && is_export_p (dep2, bb)));

  return (is_export_p (dep1)) || (dep2 && is_export_p (dep2));
}

// Return TRUE if NAME can be recomputed on edge E.  If any direct dependant
// is exported on edge E, it may change the computed value of NAME.

bool
gori_compute::may_recompute_p (tree name, edge e)
{
  gcc_checking_assert (e);
  return may_recompute_p (name, e->src);
}


// Return TRUE if a range can be calculated or recomputed for NAME on any
// edge exiting BB.

bool
gori_compute::has_edge_range_p (tree name, basic_block bb)
{
  // Check if NAME is an export or can be recomputed.
  if (bb)
    return is_export_p (name, bb) || may_recompute_p (name, bb);

  // If no block is specified, check for anywhere in the IL.
  return is_export_p (name) || may_recompute_p (name);
}

// Return TRUE if a range can be calculated or recomputed for NAME on edge E.

bool
gori_compute::has_edge_range_p (tree name, edge e)
{
  gcc_checking_assert (e);
  return has_edge_range_p (name, e->src);
}

// Calculate a range on edge E and return it in R.  Try to evaluate a
// range for NAME on this edge.  Return FALSE if this is either not a
// control edge or NAME is not defined by this edge.

bool
gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name,
				     range_query &q)
{
  int_range_max lhs;
  unsigned idx;

  if ((e->flags & m_not_executable_flag))
    {
      r.set_undefined ();
      if (dump_file && (dump_flags & TDF_DETAILS))
	  fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n",
		   e->src->index, e->dest->index);
      return true;
    }

  gcc_checking_assert (gimple_range_ssa_p (name));
  // Determine if there is an outgoing edge.
  gimple *stmt = outgoing.edge_range_p (lhs, e);
  if (!stmt)
    return false;

  fur_stmt src (stmt, &q);
  // If NAME can be calculated on the edge, use that.
  if (is_export_p (name, e->src))
    {
      bool res;
      if ((idx = tracer.header ("outgoing_edge")))
	{
	  fprintf (dump_file, " for ");
	  print_generic_expr (dump_file, name, TDF_SLIM);
	  fprintf (dump_file, " on edge %d->%d\n",
		   e->src->index, e->dest->index);
	}
      if ((res = compute_operand_range (r, stmt, lhs, name, src)))
	{
	  // Sometimes compatible types get interchanged. See PR97360.
	  // Make sure we are returning the type of the thing we asked for.
	  if (!r.undefined_p () && r.type () != TREE_TYPE (name))
	    {
	      gcc_checking_assert (range_compatible_p (r.type (),
						       TREE_TYPE (name)));
	      range_cast (r, TREE_TYPE (name));
	    }
	}
      if (idx)
	tracer.trailer (idx, "outgoing_edge", res, name, r);
      return res;
    }
  // If NAME isn't exported, check if it can be recomputed.
  else if (may_recompute_p (name, e))
    {
      gimple *def_stmt = SSA_NAME_DEF_STMT (name);

      if ((idx = tracer.header ("recomputation")))
	{
	  fprintf (dump_file, " attempt on edge %d->%d for ",
		   e->src->index, e->dest->index);
	  print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
	}
      // Simply calculate DEF_STMT on edge E using the range query Q.
      fold_range (r, def_stmt, e, &q);
      if (idx)
	tracer.trailer (idx, "recomputation", true, name, r);
      return true;
    }
  return false;
}

// Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
// to further resolve R1 and R2 if there are any dependencies between
// OP1 and COND or OP2 and COND.  All values can are to be calculated using SRC
// as the origination source location for operands..
// Effectively, use COND an the edge condition and solve for OP1 on the true
// edge and OP2 on the false edge.

bool
gori_compute::condexpr_adjust (irange &r1, irange &r2, gimple *, tree cond,
			       tree op1, tree op2, fur_source &src)
{
  int_range_max tmp, cond_true, cond_false;
  tree ssa1 = gimple_range_ssa_p (op1);
  tree ssa2 = gimple_range_ssa_p (op2);
  if (!ssa1 && !ssa2)
    return false;
  if (!COMPARISON_CLASS_P (cond))
    return false;
  tree type = TREE_TYPE (TREE_OPERAND (cond, 0));
  if (!range_compatible_p (type, TREE_TYPE (TREE_OPERAND (cond, 1))))
    return false;
  range_operator *hand = range_op_handler (TREE_CODE (cond), type);
  if (!hand)
    return false;

  tree c1 = gimple_range_ssa_p (TREE_OPERAND (cond, 0));
  tree c2 = gimple_range_ssa_p (TREE_OPERAND (cond, 1));

  // Only solve if there is one SSA name in the condition.
  if ((!c1 && !c2) || (c1 && c2))
    return false;

  // Pick up the current values of each part of the condition.
  int_range_max cl, cr;
  src.get_operand (cl, TREE_OPERAND (cond, 0));
  src.get_operand (cr, TREE_OPERAND (cond, 1));

  tree cond_name = c1 ? c1 : c2;
  gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name);

  // Evaluate the value of COND_NAME on the true and false edges, using either
  // the op1 or op2 routines based on its location.
  if (c1)
    {
      if (!hand->op1_range (cond_false, type, m_bool_zero, cr))
	return false;
      if (!hand->op1_range (cond_true, type, m_bool_one, cr))
	return false;
      cond_false.intersect (cl);
      cond_true.intersect (cl);
    }
  else
    {
      if (!hand->op2_range (cond_false, type, m_bool_zero, cl))
	return false;
      if (!hand->op2_range (cond_true, type, m_bool_one, cl))
	return false;
      cond_false.intersect (cr);
      cond_true.intersect (cr);
    }

  unsigned idx;
  if ((idx = tracer.header ("cond_expr evaluation : ")))
    {
      fprintf (dump_file, " range1 = ");
      r1.dump (dump_file);
      fprintf (dump_file, ", range2 = ");
      r1.dump (dump_file);
      fprintf (dump_file, "\n");
    }

   // Now solve for SSA1 or SSA2 if they are in the dependency chain.
   if (ssa1 && in_chain_p (ssa1, cond_name))
    {
      if (compute_operand_range (tmp, def_stmt, cond_true, ssa1, src))
	r1.intersect (tmp);
    }
  if (ssa2 && in_chain_p (ssa2, cond_name))
    {
      if (compute_operand_range (tmp, def_stmt, cond_false, ssa2, src))
	r2.intersect (tmp);
    }
  if (idx)
    {
      tracer.print (idx, "outgoing: range1 = ");
      r1.dump (dump_file);
      fprintf (dump_file, ", range2 = ");
      r1.dump (dump_file);
      fprintf (dump_file, "\n");
      tracer.trailer (idx, "cond_expr", true, cond_name, cond_true);
    }
  return true;
}

// Dump what is known to GORI computes to listing file F.

void
gori_compute::dump (FILE *f)
{
  gori_map::dump (f);
}

// ------------------------------------------------------------------------
//  GORI iterator.  Although we have bitmap iterators, don't expose that it
//  is currently a bitmap.  Use an export iterator to hide future changes.

// Construct a basic iterator over an export bitmap.

gori_export_iterator::gori_export_iterator (bitmap b)
{
  bm = b;
  if (b)
    bmp_iter_set_init (&bi, b, 1, &y);
}


// Move to the next export bitmap spot.

void
gori_export_iterator::next ()
{
  bmp_iter_next (&bi, &y);
}


// Fetch the name of the next export in the export list.  Return NULL if
// iteration is done.

tree
gori_export_iterator::get_name ()
{
  if (!bm)
    return NULL_TREE;

  while (bmp_iter_set (&bi, &y))
    {
      tree t = ssa_name (y);
      if (t)
	return t;
      next ();
    }
  return NULL_TREE;
}