gcc/ipa-cp.c

/* Interprocedural constant propagation
   Copyright (C) 2005-2021 Free Software Foundation, Inc.

   Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
   <mjambor@suse.cz>

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/>.  */

/* Interprocedural constant propagation (IPA-CP).

   The goal of this transformation is to

   1) discover functions which are always invoked with some arguments with the
      same known constant values and modify the functions so that the
      subsequent optimizations can take advantage of the knowledge, and

   2) partial specialization - create specialized versions of functions
      transformed in this way if some parameters are known constants only in
      certain contexts but the estimated tradeoff between speedup and cost size
      is deemed good.

   The algorithm also propagates types and attempts to perform type based
   devirtualization.  Types are propagated much like constants.

   The algorithm basically consists of three stages.  In the first, functions
   are analyzed one at a time and jump functions are constructed for all known
   call-sites.  In the second phase, the pass propagates information from the
   jump functions across the call to reveal what values are available at what
   call sites, performs estimations of effects of known values on functions and
   their callees, and finally decides what specialized extra versions should be
   created.  In the third, the special versions materialize and appropriate
   calls are redirected.

   The algorithm used is to a certain extent based on "Interprocedural Constant
   Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
   Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
   Cooper, Mary W. Hall, and Ken Kennedy.


   First stage - intraprocedural analysis
   =======================================

   This phase computes jump_function and modification flags.

   A jump function for a call-site represents the values passed as an actual
   arguments of a given call-site. In principle, there are three types of
   values:

   Pass through - the caller's formal parameter is passed as an actual
		  argument, plus an operation on it can be performed.
   Constant - a constant is passed as an actual argument.
   Unknown - neither of the above.

   All jump function types are described in detail in ipa-prop.h, together with
   the data structures that represent them and methods of accessing them.

   ipcp_generate_summary() is the main function of the first stage.

   Second stage - interprocedural analysis
   ========================================

   This stage is itself divided into two phases.  In the first, we propagate
   known values over the call graph, in the second, we make cloning decisions.
   It uses a different algorithm than the original Callahan's paper.

   First, we traverse the functions topologically from callers to callees and,
   for each strongly connected component (SCC), we propagate constants
   according to previously computed jump functions.  We also record what known
   values depend on other known values and estimate local effects.  Finally, we
   propagate cumulative information about these effects from dependent values
   to those on which they depend.

   Second, we again traverse the call graph in the same topological order and
   make clones for functions which we know are called with the same values in
   all contexts and decide about extra specialized clones of functions just for
   some contexts - these decisions are based on both local estimates and
   cumulative estimates propagated from callees.

   ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
   third stage.

   Third phase - materialization of clones, call statement updates.
   ============================================

   This stage is currently performed by call graph code (mainly in cgraphunit.c
   and tree-inline.c) according to instructions inserted to the call graph by
   the second stage.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple-expr.h"
#include "gimple.h"
#include "predict.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "cgraph.h"
#include "diagnostic.h"
#include "fold-const.h"
#include "gimple-fold.h"
#include "symbol-summary.h"
#include "tree-vrp.h"
#include "ipa-prop.h"
#include "tree-pretty-print.h"
#include "tree-inline.h"
#include "ipa-fnsummary.h"
#include "ipa-utils.h"
#include "tree-ssa-ccp.h"
#include "stringpool.h"
#include "attribs.h"
#include "dbgcnt.h"
#include "symtab-clones.h"

template <typename valtype> class ipcp_value;

/* Describes a particular source for an IPA-CP value.  */

template <typename valtype>
struct ipcp_value_source
{
public:
  /* Aggregate offset of the source, negative if the source is scalar value of
     the argument itself.  */
  HOST_WIDE_INT offset;
  /* The incoming edge that brought the value.  */
  cgraph_edge *cs;
  /* If the jump function that resulted into his value was a pass-through or an
     ancestor, this is the ipcp_value of the caller from which the described
     value has been derived.  Otherwise it is NULL.  */
  ipcp_value<valtype> *val;
  /* Next pointer in a linked list of sources of a value.  */
  ipcp_value_source *next;
  /* If the jump function that resulted into his value was a pass-through or an
     ancestor, this is the index of the parameter of the caller the jump
     function references.  */
  int index;
};

/* Common ancestor for all ipcp_value instantiations.  */

class ipcp_value_base
{
public:
  /* Time benefit and that specializing the function for this value would bring
     about in this function alone.  */
  sreal local_time_benefit;
  /* Time benefit that specializing the function for this value can bring about
     in it's callees.  */
  sreal prop_time_benefit;
  /* Size cost that specializing the function for this value would bring about
     in this function alone.  */
  int local_size_cost;
  /* Size cost that specializing the function for this value can bring about in
     it's callees.  */
  int prop_size_cost;

  ipcp_value_base ()
    : local_time_benefit (0), prop_time_benefit (0),
      local_size_cost (0), prop_size_cost (0) {}
};

/* Describes one particular value stored in struct ipcp_lattice.  */

template <typename valtype>
class ipcp_value : public ipcp_value_base
{
public:
  /* The actual value for the given parameter.  */
  valtype value;
  /* The list of sources from which this value originates.  */
  ipcp_value_source <valtype> *sources = nullptr;
  /* Next pointers in a linked list of all values in a lattice.  */
  ipcp_value *next = nullptr;
  /* Next pointers in a linked list of values in a strongly connected component
     of values. */
  ipcp_value *scc_next = nullptr;
  /* Next pointers in a linked list of SCCs of values sorted topologically
     according their sources.  */
  ipcp_value  *topo_next = nullptr;
  /* A specialized node created for this value, NULL if none has been (so far)
     created.  */
  cgraph_node *spec_node = nullptr;
  /* Depth first search number and low link for topological sorting of
     values.  */
  int dfs = 0;
  int low_link = 0;
  /* SCC number to identify values which recursively feed into each other.
     Values in the same SCC have the same SCC number.  */
  int scc_no = 0;
  /* Non zero if the value is generated from another value in the same lattice
     for a self-recursive call, the actual number is how many times the
     operation has been performed.  In the unlikely event of the value being
     present in two chains fo self-recursive value generation chains, it is the
     maximum.  */
  unsigned self_recursion_generated_level = 0;
  /* True if this value is currently on the topo-sort stack.  */
  bool on_stack = false;

  void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
		   HOST_WIDE_INT offset);

  /* Return true if both THIS value and O feed into each other.  */

  bool same_scc (const ipcp_value<valtype> *o)
  {
    return o->scc_no == scc_no;
  }

/* Return true, if a this value has been generated for a self-recursive call as
   a result of an arithmetic pass-through jump-function acting on a value in
   the same lattice function.  */

  bool self_recursion_generated_p ()
  {
    return self_recursion_generated_level > 0;
  }
};

/* Lattice describing potential values of a formal parameter of a function, or
   a part of an aggregate.  TOP is represented by a lattice with zero values
   and with contains_variable and bottom flags cleared.  BOTTOM is represented
   by a lattice with the bottom flag set.  In that case, values and
   contains_variable flag should be disregarded.  */

template <typename valtype>
struct ipcp_lattice
{
public:
  /* The list of known values and types in this lattice.  Note that values are
     not deallocated if a lattice is set to bottom because there may be value
     sources referencing them.  */
  ipcp_value<valtype> *values;
  /* Number of known values and types in this lattice.  */
  int values_count;
  /* The lattice contains a variable component (in addition to values).  */
  bool contains_variable;
  /* The value of the lattice is bottom (i.e. variable and unusable for any
     propagation).  */
  bool bottom;

  inline bool is_single_const ();
  inline bool set_to_bottom ();
  inline bool set_contains_variable ();
  bool add_value (valtype newval, cgraph_edge *cs,
		  ipcp_value<valtype> *src_val = NULL,
		  int src_idx = 0, HOST_WIDE_INT offset = -1,
		  ipcp_value<valtype> **val_p = NULL,
		  unsigned same_lat_gen_level = 0);
  void print (FILE * f, bool dump_sources, bool dump_benefits);
};

/* Lattice of tree values with an offset to describe a part of an
   aggregate.  */

struct ipcp_agg_lattice : public ipcp_lattice<tree>
{
public:
  /* Offset that is being described by this lattice. */
  HOST_WIDE_INT offset;
  /* Size so that we don't have to re-compute it every time we traverse the
     list.  Must correspond to TYPE_SIZE of all lat values.  */
  HOST_WIDE_INT size;
  /* Next element of the linked list.  */
  struct ipcp_agg_lattice *next;
};

/* Lattice of known bits, only capable of holding one value.
   Bitwise constant propagation propagates which bits of a
   value are constant.
   For eg:
   int f(int x)
   {
     return some_op (x);
   }

   int f1(int y)
   {
     if (cond)
      return f (y & 0xff);
     else
      return f (y & 0xf);
   }

   In the above case, the param 'x' will always have all
   the bits (except the bits in lsb) set to 0.
   Hence the mask of 'x' would be 0xff. The mask
   reflects that the bits in lsb are unknown.
   The actual propagated value is given by m_value & ~m_mask.  */

class ipcp_bits_lattice
{
public:
  bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; }
  bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; }
  bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; }
  bool set_to_bottom ();
  bool set_to_constant (widest_int, widest_int);

  widest_int get_value () { return m_value; }
  widest_int get_mask () { return m_mask; }

  bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
		  enum tree_code, tree);

  bool meet_with (widest_int, widest_int, unsigned);

  void print (FILE *);

private:
  enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val;

  /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
     If a bit in mask is set to 0, then the corresponding bit in
     value is known to be constant.  */
  widest_int m_value, m_mask;

  bool meet_with_1 (widest_int, widest_int, unsigned);
  void get_value_and_mask (tree, widest_int *, widest_int *);
};

/* Lattice of value ranges.  */

class ipcp_vr_lattice
{
public:
  value_range m_vr;

  inline bool bottom_p () const;
  inline bool top_p () const;
  inline bool set_to_bottom ();
  bool meet_with (const value_range *p_vr);
  bool meet_with (const ipcp_vr_lattice &other);
  void init () { gcc_assert (m_vr.undefined_p ()); }
  void print (FILE * f);

private:
  bool meet_with_1 (const value_range *other_vr);
};

/* Structure containing lattices for a parameter itself and for pieces of
   aggregates that are passed in the parameter or by a reference in a parameter
   plus some other useful flags.  */

class ipcp_param_lattices
{
public:
  /* Lattice describing the value of the parameter itself.  */
  ipcp_lattice<tree> itself;
  /* Lattice describing the polymorphic contexts of a parameter.  */
  ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
  /* Lattices describing aggregate parts.  */
  ipcp_agg_lattice *aggs;
  /* Lattice describing known bits.  */
  ipcp_bits_lattice bits_lattice;
  /* Lattice describing value range.  */
  ipcp_vr_lattice m_value_range;
  /* Number of aggregate lattices */
  int aggs_count;
  /* True if aggregate data were passed by reference (as opposed to by
     value).  */
  bool aggs_by_ref;
  /* All aggregate lattices contain a variable component (in addition to
     values).  */
  bool aggs_contain_variable;
  /* The value of all aggregate lattices is bottom (i.e. variable and unusable
     for any propagation).  */
  bool aggs_bottom;

  /* There is a virtual call based on this parameter.  */
  bool virt_call;
};

/* Allocation pools for values and their sources in ipa-cp.  */

object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
  ("IPA-CP constant values");

object_allocator<ipcp_value<ipa_polymorphic_call_context> >
  ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");

object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
  ("IPA-CP value sources");

object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
  ("IPA_CP aggregate lattices");

/* Maximal count found in program.  */

static profile_count max_count;

/* Original overall size of the program.  */

static long overall_size, orig_overall_size;

/* Node name to unique clone suffix number map.  */
static hash_map<const char *, unsigned> *clone_num_suffixes;

/* Return the param lattices structure corresponding to the Ith formal
   parameter of the function described by INFO.  */
static inline class ipcp_param_lattices *
ipa_get_parm_lattices (class ipa_node_params *info, int i)
{
  gcc_assert (i >= 0 && i < ipa_get_param_count (info));
  gcc_checking_assert (!info->ipcp_orig_node);
  gcc_checking_assert (info->lattices);
  return &(info->lattices[i]);
}

/* Return the lattice corresponding to the scalar value of the Ith formal
   parameter of the function described by INFO.  */
static inline ipcp_lattice<tree> *
ipa_get_scalar_lat (class ipa_node_params *info, int i)
{
  class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
  return &plats->itself;
}

/* Return the lattice corresponding to the scalar value of the Ith formal
   parameter of the function described by INFO.  */
static inline ipcp_lattice<ipa_polymorphic_call_context> *
ipa_get_poly_ctx_lat (class ipa_node_params *info, int i)
{
  class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
  return &plats->ctxlat;
}

/* Return whether LAT is a lattice with a single constant and without an
   undefined value.  */

template <typename valtype>
inline bool
ipcp_lattice<valtype>::is_single_const ()
{
  if (bottom || contains_variable || values_count != 1)
    return false;
  else
    return true;
}

/* Print V which is extracted from a value in a lattice to F.  */

static void
print_ipcp_constant_value (FILE * f, tree v)
{
  if (TREE_CODE (v) == ADDR_EXPR
      && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
    {
      fprintf (f, "& ");
      print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)));
    }
  else
    print_generic_expr (f, v);
}

/* Print V which is extracted from a value in a lattice to F.  */

static void
print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
{
  v.dump(f, false);
}

/* Print a lattice LAT to F.  */

template <typename valtype>
void
ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
{
  ipcp_value<valtype> *val;
  bool prev = false;

  if (bottom)
    {
      fprintf (f, "BOTTOM\n");
      return;
    }

  if (!values_count && !contains_variable)
    {
      fprintf (f, "TOP\n");
      return;
    }

  if (contains_variable)
    {
      fprintf (f, "VARIABLE");
      prev = true;
      if (dump_benefits)
	fprintf (f, "\n");
    }

  for (val = values; val; val = val->next)
    {
      if (dump_benefits && prev)
	fprintf (f, "               ");
      else if (!dump_benefits && prev)
	fprintf (f, ", ");
      else
	prev = true;

      print_ipcp_constant_value (f, val->value);

      if (dump_sources)
	{
	  ipcp_value_source<valtype> *s;

	  if (val->self_recursion_generated_p ())
	    fprintf (f, " [self_gen(%i), from:",
		     val->self_recursion_generated_level);
	  else
	    fprintf (f, " [scc: %i, from:", val->scc_no);
	  for (s = val->sources; s; s = s->next)
	    fprintf (f, " %i(%f)", s->cs->caller->order,
		     s->cs->sreal_frequency ().to_double ());
	  fprintf (f, "]");
	}

      if (dump_benefits)
	fprintf (f, " [loc_time: %g, loc_size: %i, "
		 "prop_time: %g, prop_size: %i]\n",
		 val->local_time_benefit.to_double (), val->local_size_cost,
		 val->prop_time_benefit.to_double (), val->prop_size_cost);
    }
  if (!dump_benefits)
    fprintf (f, "\n");
}

void
ipcp_bits_lattice::print (FILE *f)
{
  if (top_p ())
    fprintf (f, "         Bits unknown (TOP)\n");
  else if (bottom_p ())
    fprintf (f, "         Bits unusable (BOTTOM)\n");
  else
    {
      fprintf (f, "         Bits: value = "); print_hex (get_value (), f);
      fprintf (f, ", mask = "); print_hex (get_mask (), f);
      fprintf (f, "\n");
    }
}

/* Print value range lattice to F.  */

void
ipcp_vr_lattice::print (FILE * f)
{
  dump_value_range (f, &m_vr);
}

/* Print all ipcp_lattices of all functions to F.  */

static void
print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
{
  struct cgraph_node *node;
  int i, count;

  fprintf (f, "\nLattices:\n");
  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
    {
      class ipa_node_params *info;

      info = ipa_node_params_sum->get (node);
      /* Skip unoptimized functions and constprop clones since we don't make
	 lattices for them.  */
      if (!info || info->ipcp_orig_node)
	continue;
      fprintf (f, "  Node: %s:\n", node->dump_name ());
      count = ipa_get_param_count (info);
      for (i = 0; i < count; i++)
	{
	  struct ipcp_agg_lattice *aglat;
	  class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
	  fprintf (f, "    param [%d]: ", i);
	  plats->itself.print (f, dump_sources, dump_benefits);
	  fprintf (f, "         ctxs: ");
	  plats->ctxlat.print (f, dump_sources, dump_benefits);
	  plats->bits_lattice.print (f);
	  fprintf (f, "         ");
	  plats->m_value_range.print (f);
	  fprintf (f, "\n");
	  if (plats->virt_call)
	    fprintf (f, "        virt_call flag set\n");

	  if (plats->aggs_bottom)
	    {
	      fprintf (f, "        AGGS BOTTOM\n");
	      continue;
	    }
	  if (plats->aggs_contain_variable)
	    fprintf (f, "        AGGS VARIABLE\n");
	  for (aglat = plats->aggs; aglat; aglat = aglat->next)
	    {
	      fprintf (f, "        %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
		       plats->aggs_by_ref ? "ref " : "", aglat->offset);
	      aglat->print (f, dump_sources, dump_benefits);
	    }
	}
    }
}

/* Determine whether it is at all technically possible to create clones of NODE
   and store this information in the ipa_node_params structure associated
   with NODE.  */

static void
determine_versionability (struct cgraph_node *node,
			  class ipa_node_params *info)
{
  const char *reason = NULL;

  /* There are a number of generic reasons functions cannot be versioned.  We
     also cannot remove parameters if there are type attributes such as fnspec
     present.  */
  if (node->alias || node->thunk)
    reason = "alias or thunk";
  else if (!node->versionable)
    reason = "not a tree_versionable_function";
  else if (node->get_availability () <= AVAIL_INTERPOSABLE)
    reason = "insufficient body availability";
  else if (!opt_for_fn (node->decl, optimize)
	   || !opt_for_fn (node->decl, flag_ipa_cp))
    reason = "non-optimized function";
  else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
    {
      /* Ideally we should clone the SIMD clones themselves and create
	 vector copies of them, so IPA-cp and SIMD clones can happily
	 coexist, but that may not be worth the effort.  */
      reason = "function has SIMD clones";
    }
  else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node->decl)))
    {
      /* Ideally we should clone the target clones themselves and create
	 copies of them, so IPA-cp and target clones can happily
	 coexist, but that may not be worth the effort.  */
      reason = "function target_clones attribute";
    }
  /* Don't clone decls local to a comdat group; it breaks and for C++
     decloned constructors, inlining is always better anyway.  */
  else if (node->comdat_local_p ())
    reason = "comdat-local function";
  else if (node->calls_comdat_local)
    {
      /* TODO: call is versionable if we make sure that all
	 callers are inside of a comdat group.  */
      reason = "calls comdat-local function";
    }

  /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
     work only when inlined.  Cloning them may still lead to better code
     because ipa-cp will not give up on cloning further.  If the function is
     external this however leads to wrong code because we may end up producing
     offline copy of the function.  */
  if (DECL_EXTERNAL (node->decl))
    for (cgraph_edge *edge = node->callees; !reason && edge;
	 edge = edge->next_callee)
      if (fndecl_built_in_p (edge->callee->decl, BUILT_IN_NORMAL))
        {
	  if (DECL_FUNCTION_CODE (edge->callee->decl) == BUILT_IN_VA_ARG_PACK)
	    reason = "external function which calls va_arg_pack";
	  if (DECL_FUNCTION_CODE (edge->callee->decl)
	      == BUILT_IN_VA_ARG_PACK_LEN)
	    reason = "external function which calls va_arg_pack_len";
        }

  if (reason && dump_file && !node->alias && !node->thunk)
    fprintf (dump_file, "Function %s is not versionable, reason: %s.\n",
	     node->dump_name (), reason);

  info->versionable = (reason == NULL);
}

/* Return true if it is at all technically possible to create clones of a
   NODE.  */

static bool
ipcp_versionable_function_p (struct cgraph_node *node)
{
  ipa_node_params *info = ipa_node_params_sum->get (node);
  return info && info->versionable;
}

/* Structure holding accumulated information about callers of a node.  */

struct caller_statistics
{
  profile_count count_sum;
  sreal freq_sum;
  int n_calls, n_hot_calls;
};

/* Initialize fields of STAT to zeroes.  */

static inline void
init_caller_stats (struct caller_statistics *stats)
{
  stats->count_sum = profile_count::zero ();
  stats->n_calls = 0;
  stats->n_hot_calls = 0;
  stats->freq_sum = 0;
}

/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
   non-thunk incoming edges to NODE.  */

static bool
gather_caller_stats (struct cgraph_node *node, void *data)
{
  struct caller_statistics *stats = (struct caller_statistics *) data;
  struct cgraph_edge *cs;

  for (cs = node->callers; cs; cs = cs->next_caller)
    if (!cs->caller->thunk)
      {
        if (cs->count.ipa ().initialized_p ())
	  stats->count_sum += cs->count.ipa ();
	stats->freq_sum += cs->sreal_frequency ();
	stats->n_calls++;
	if (cs->maybe_hot_p ())
	  stats->n_hot_calls ++;
      }
  return false;

}

/* Return true if this NODE is viable candidate for cloning.  */

static bool
ipcp_cloning_candidate_p (struct cgraph_node *node)
{
  struct caller_statistics stats;

  gcc_checking_assert (node->has_gimple_body_p ());

  if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
    {
      if (dump_file)
	fprintf (dump_file, "Not considering %s for cloning; "
		 "-fipa-cp-clone disabled.\n",
		 node->dump_name ());
      return false;
    }

  if (node->optimize_for_size_p ())
    {
      if (dump_file)
	fprintf (dump_file, "Not considering %s for cloning; "
		 "optimizing it for size.\n",
		 node->dump_name ());
      return false;
    }

  init_caller_stats (&stats);
  node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);

  if (ipa_size_summaries->get (node)->self_size < stats.n_calls)
    {
      if (dump_file)
	fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
		 node->dump_name ());
      return true;
    }

  /* When profile is available and function is hot, propagate into it even if
     calls seems cold; constant propagation can improve function's speed
     significantly.  */
  if (max_count > profile_count::zero ())
    {
      if (stats.count_sum > node->count.ipa ().apply_scale (90, 100))
	{
	  if (dump_file)
	    fprintf (dump_file, "Considering %s for cloning; "
		     "usually called directly.\n",
		     node->dump_name ());
	  return true;
	}
    }
  if (!stats.n_hot_calls)
    {
      if (dump_file)
	fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
		 node->dump_name ());
      return false;
    }
  if (dump_file)
    fprintf (dump_file, "Considering %s for cloning.\n",
	     node->dump_name ());
  return true;
}

template <typename valtype>
class value_topo_info
{
public:
  /* Head of the linked list of topologically sorted values. */
  ipcp_value<valtype> *values_topo;
  /* Stack for creating SCCs, represented by a linked list too.  */
  ipcp_value<valtype> *stack;
  /* Counter driving the algorithm in add_val_to_toposort.  */
  int dfs_counter;

  value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
  {}
  void add_val (ipcp_value<valtype> *cur_val);
  void propagate_effects ();
};

/* Arrays representing a topological ordering of call graph nodes and a stack
   of nodes used during constant propagation and also data required to perform
   topological sort of values and propagation of benefits in the determined
   order.  */

class ipa_topo_info
{
public:
  /* Array with obtained topological order of cgraph nodes.  */
  struct cgraph_node **order;
  /* Stack of cgraph nodes used during propagation within SCC until all values
     in the SCC stabilize.  */
  struct cgraph_node **stack;
  int nnodes, stack_top;

  value_topo_info<tree> constants;
  value_topo_info<ipa_polymorphic_call_context> contexts;

  ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
    constants ()
  {}
};

/* Skip edges from and to nodes without ipa_cp enabled.
   Ignore not available symbols.  */

static bool
ignore_edge_p (cgraph_edge *e)
{
  enum availability avail;
  cgraph_node *ultimate_target
    = e->callee->function_or_virtual_thunk_symbol (&avail, e->caller);

  return (avail <= AVAIL_INTERPOSABLE
	  || !opt_for_fn (ultimate_target->decl, optimize)
	  || !opt_for_fn (ultimate_target->decl, flag_ipa_cp));
}

/* Allocate the arrays in TOPO and topologically sort the nodes into order.  */

static void
build_toporder_info (class ipa_topo_info *topo)
{
  topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
  topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);

  gcc_checking_assert (topo->stack_top == 0);
  topo->nnodes = ipa_reduced_postorder (topo->order, true,
					ignore_edge_p);
}

/* Free information about strongly connected components and the arrays in
   TOPO.  */

static void
free_toporder_info (class ipa_topo_info *topo)
{
  ipa_free_postorder_info ();
  free (topo->order);
  free (topo->stack);
}

/* Add NODE to the stack in TOPO, unless it is already there.  */

static inline void
push_node_to_stack (class ipa_topo_info *topo, struct cgraph_node *node)
{
  ipa_node_params *info = ipa_node_params_sum->get (node);
  if (info->node_enqueued)
    return;
  info->node_enqueued = 1;
  topo->stack[topo->stack_top++] = node;
}

/* Pop a node from the stack in TOPO and return it or return NULL if the stack
   is empty.  */

static struct cgraph_node *
pop_node_from_stack (class ipa_topo_info *topo)
{
  if (topo->stack_top)
    {
      struct cgraph_node *node;
      topo->stack_top--;
      node = topo->stack[topo->stack_top];
      ipa_node_params_sum->get (node)->node_enqueued = 0;
      return node;
    }
  else
    return NULL;
}

/* Set lattice LAT to bottom and return true if it previously was not set as
   such.  */

template <typename valtype>
inline bool
ipcp_lattice<valtype>::set_to_bottom ()
{
  bool ret = !bottom;
  bottom = true;
  return ret;
}

/* Mark lattice as containing an unknown value and return true if it previously
   was not marked as such.  */

template <typename valtype>
inline bool
ipcp_lattice<valtype>::set_contains_variable ()
{
  bool ret = !contains_variable;
  contains_variable = true;
  return ret;
}

/* Set all aggregate lattices in PLATS to bottom and return true if they were
   not previously set as such.  */

static inline bool
set_agg_lats_to_bottom (class ipcp_param_lattices *plats)
{
  bool ret = !plats->aggs_bottom;
  plats->aggs_bottom = true;
  return ret;
}

/* Mark all aggregate lattices in PLATS as containing an unknown value and
   return true if they were not previously marked as such.  */

static inline bool
set_agg_lats_contain_variable (class ipcp_param_lattices *plats)
{
  bool ret = !plats->aggs_contain_variable;
  plats->aggs_contain_variable = true;
  return ret;
}

bool
ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
{
  return meet_with_1 (&other.m_vr);
}

/* Meet the current value of the lattice with value range described by VR
   lattice.  */

bool
ipcp_vr_lattice::meet_with (const value_range *p_vr)
{
  return meet_with_1 (p_vr);
}

/* Meet the current value of the lattice with value range described by
   OTHER_VR lattice.  Return TRUE if anything changed.  */

bool
ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
{
  if (bottom_p ())
    return false;

  if (other_vr->varying_p ())
    return set_to_bottom ();

  value_range save (m_vr);
  m_vr.union_ (other_vr);
  return !m_vr.equal_p (save);
}

/* Return true if value range information in the lattice is yet unknown.  */

bool
ipcp_vr_lattice::top_p () const
{
  return m_vr.undefined_p ();
}

/* Return true if value range information in the lattice is known to be
   unusable.  */

bool
ipcp_vr_lattice::bottom_p () const
{
  return m_vr.varying_p ();
}

/* Set value range information in the lattice to bottom.  Return true if it
   previously was in a different state.  */

bool
ipcp_vr_lattice::set_to_bottom ()
{
  if (m_vr.varying_p ())
    return false;
  /* ?? We create all sorts of VARYING ranges for floats, structures,
     and other types which we cannot handle as ranges.  We should
     probably avoid handling them throughout the pass, but it's easier
     to create a sensible VARYING here and let the lattice
     propagate.  */
  m_vr.set_varying (integer_type_node);
  return true;
}

/* Set lattice value to bottom, if it already isn't the case.  */

bool
ipcp_bits_lattice::set_to_bottom ()
{
  if (bottom_p ())
    return false;
  m_lattice_val = IPA_BITS_VARYING;
  m_value = 0;
  m_mask = -1;
  return true;
}

/* Set to constant if it isn't already. Only meant to be called
   when switching state from TOP.  */

bool
ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask)
{
  gcc_assert (top_p ());
  m_lattice_val = IPA_BITS_CONSTANT;
  m_value = wi::bit_and (wi::bit_not (mask), value);
  m_mask = mask;
  return true;
}

/* Convert operand to value, mask form.  */

void
ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
{
  wide_int get_nonzero_bits (const_tree);

  if (TREE_CODE (operand) == INTEGER_CST)
    {
      *valuep = wi::to_widest (operand);
      *maskp = 0;
    }
  else
    {
      *valuep = 0;
      *maskp = -1;
    }
}

/* Meet operation, similar to ccp_lattice_meet, we xor values
   if this->value, value have different values at same bit positions, we want
   to drop that bit to varying. Return true if mask is changed.
   This function assumes that the lattice value is in CONSTANT state  */

bool
ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask,
				unsigned precision)
{
  gcc_assert (constant_p ());

  widest_int old_mask = m_mask;
  m_mask = (m_mask | mask) | (m_value ^ value);
  m_value &= ~m_mask;

  if (wi::sext (m_mask, precision) == -1)
    return set_to_bottom ();

  return m_mask != old_mask;
}

/* Meet the bits lattice with operand
   described by <value, mask, sgn, precision.  */

bool
ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
			      unsigned precision)
{
  if (bottom_p ())
    return false;

  if (top_p ())
    {
      if (wi::sext (mask, precision) == -1)
	return set_to_bottom ();
      return set_to_constant (value, mask);
    }

  return meet_with_1 (value, mask, precision);
}

/* Meet bits lattice with the result of bit_value_binop (other, operand)
   if code is binary operation or bit_value_unop (other) if code is unary op.
   In the case when code is nop_expr, no adjustment is required. */

bool
ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision,
			      signop sgn, enum tree_code code, tree operand)
{
  if (other.bottom_p ())
    return set_to_bottom ();

  if (bottom_p () || other.top_p ())
    return false;

  widest_int adjusted_value, adjusted_mask;

  if (TREE_CODE_CLASS (code) == tcc_binary)
    {
      tree type = TREE_TYPE (operand);
      widest_int o_value, o_mask;
      get_value_and_mask (operand, &o_value, &o_mask);

      bit_value_binop (code, sgn, precision, &adjusted_value, &adjusted_mask,
		       sgn, precision, other.get_value (), other.get_mask (),
		       TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);

      if (wi::sext (adjusted_mask, precision) == -1)
	return set_to_bottom ();
    }

  else if (TREE_CODE_CLASS (code) == tcc_unary)
    {
      bit_value_unop (code, sgn, precision, &adjusted_value,
		      &adjusted_mask, sgn, precision, other.get_value (),
		      other.get_mask ());

      if (wi::sext (adjusted_mask, precision) == -1)
	return set_to_bottom ();
    }

  else
    return set_to_bottom ();

  if (top_p ())
    {
      if (wi::sext (adjusted_mask, precision) == -1)
	return set_to_bottom ();
      return set_to_constant (adjusted_value, adjusted_mask);
    }
  else
    return meet_with_1 (adjusted_value, adjusted_mask, precision);
}

/* Mark bot aggregate and scalar lattices as containing an unknown variable,
   return true is any of them has not been marked as such so far.  */

static inline bool
set_all_contains_variable (class ipcp_param_lattices *plats)
{
  bool ret;
  ret = plats->itself.set_contains_variable ();
  ret |= plats->ctxlat.set_contains_variable ();
  ret |= set_agg_lats_contain_variable (plats);
  ret |= plats->bits_lattice.set_to_bottom ();
  ret |= plats->m_value_range.set_to_bottom ();
  return ret;
}

/* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
   points to by the number of callers to NODE.  */

static bool
count_callers (cgraph_node *node, void *data)
{
  int *caller_count = (int *) data;

  for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
    /* Local thunks can be handled transparently, but if the thunk cannot
       be optimized out, count it as a real use.  */
    if (!cs->caller->thunk || !cs->caller->local)
      ++*caller_count;
  return false;
}

/* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
   the one caller of some other node.  Set the caller's corresponding flag.  */

static bool
set_single_call_flag (cgraph_node *node, void *)
{
  cgraph_edge *cs = node->callers;
  /* Local thunks can be handled transparently, skip them.  */
  while (cs && cs->caller->thunk && cs->caller->local)
    cs = cs->next_caller;
  if (cs)
    if (ipa_node_params* info = ipa_node_params_sum->get (cs->caller))
      {
	info->node_calling_single_call = true;
	return true;
      }
  return false;
}

/* Initialize ipcp_lattices.  */

static void
initialize_node_lattices (struct cgraph_node *node)
{
  ipa_node_params *info = ipa_node_params_sum->get (node);
  struct cgraph_edge *ie;
  bool disable = false, variable = false;
  int i;

  gcc_checking_assert (node->has_gimple_body_p ());

  if (!ipa_get_param_count (info))
    disable = true;
  else if (node->local)
    {
      int caller_count = 0;
      node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
						true);
      gcc_checking_assert (caller_count > 0);
      if (caller_count == 1)
	node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
						  NULL, true);
    }
  else
    {
      /* When cloning is allowed, we can assume that externally visible
	 functions are not called.  We will compensate this by cloning
	 later.  */
      if (ipcp_versionable_function_p (node)
	  && ipcp_cloning_candidate_p (node))
	variable = true;
      else
	disable = true;
    }

  if (dump_file && (dump_flags & TDF_DETAILS)
      && !node->alias && !node->thunk)
    {
      fprintf (dump_file, "Initializing lattices of %s\n",
	       node->dump_name ());
      if (disable || variable)
	fprintf (dump_file, "  Marking all lattices as %s\n",
		 disable ? "BOTTOM" : "VARIABLE");
    }

  auto_vec<bool, 16> surviving_params;
  bool pre_modified = false;

  clone_info *cinfo = clone_info::get (node);

  if (!disable && cinfo && cinfo->param_adjustments)
    {
      /* At the moment all IPA optimizations should use the number of
	 parameters of the prevailing decl as the m_always_copy_start.
	 Handling any other value would complicate the code below, so for the
	 time bing let's only assert it is so.  */
      gcc_assert ((cinfo->param_adjustments->m_always_copy_start
		   == ipa_get_param_count (info))
		  || cinfo->param_adjustments->m_always_copy_start < 0);

      pre_modified = true;
      cinfo->param_adjustments->get_surviving_params (&surviving_params);

      if (dump_file && (dump_flags & TDF_DETAILS)
	  && !node->alias && !node->thunk)
	{
	  bool first = true;
	  for (int j = 0; j < ipa_get_param_count (info); j++)
	    {
	      if (j < (int) surviving_params.length ()
		  && surviving_params[j])
		continue;
	      if (first)
		{
		  fprintf (dump_file,
			   "  The following parameters are dead on arrival:");
		  first = false;
		}
	      fprintf (dump_file, " %u", j);
	    }
	  if (!first)
	      fprintf (dump_file, "\n");
	}
    }

  for (i = 0; i < ipa_get_param_count (info); i++)
    {
      ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
      if (disable
	  || !ipa_get_type (info, i)
	  || (pre_modified && (surviving_params.length () <= (unsigned) i
			       || !surviving_params[i])))
	{
	  plats->itself.set_to_bottom ();
	  plats->ctxlat.set_to_bottom ();
	  set_agg_lats_to_bottom (plats);
	  plats->bits_lattice.set_to_bottom ();
	  plats->m_value_range.m_vr = value_range ();
	  plats->m_value_range.set_to_bottom ();
	}
      else
	{
	  plats->m_value_range.init ();
	  if (variable)
	    set_all_contains_variable (plats);
	}
    }

  for (ie = node->indirect_calls; ie; ie = ie->next_callee)
    if (ie->indirect_info->polymorphic
	&& ie->indirect_info->param_index >= 0)
      {
	gcc_checking_assert (ie->indirect_info->param_index >= 0);
	ipa_get_parm_lattices (info,
			       ie->indirect_info->param_index)->virt_call = 1;
      }
}

/* Return true if VALUE can be safely IPA-CP propagated to a parameter of type
   PARAM_TYPE.  */

static bool
ipacp_value_safe_for_type (tree param_type, tree value)
{
  tree val_type = TREE_TYPE (value);
  if (param_type == val_type
      || useless_type_conversion_p (param_type, val_type)
      || fold_convertible_p (param_type, value))
    return true;
  else
    return false;
}

/* Return true iff X and Y should be considered equal values by IPA-CP.  */

static bool
values_equal_for_ipcp_p (tree x, tree y)
{
  gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);

  if (x == y)
    return true;

  if (TREE_CODE (x) == ADDR_EXPR
      && TREE_CODE (y) == ADDR_EXPR
      && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
      && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
    return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
			    DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
  else
    return operand_equal_p (x, y, 0);
}

/* Return the result of a (possibly arithmetic) operation on the constant
   value INPUT.  OPERAND is 2nd operand for binary operation.  RES_TYPE is
   the type of the parameter to which the result is passed.  Return
   NULL_TREE if that cannot be determined or be considered an
   interprocedural invariant.  */

static tree
ipa_get_jf_arith_result (enum tree_code opcode, tree input, tree operand,
			 tree res_type)
{
  tree res;

  if (opcode == NOP_EXPR)
    return input;
  if (!is_gimple_ip_invariant (input))
    return NULL_TREE;

  if (opcode == ASSERT_EXPR)
    {
      if (values_equal_for_ipcp_p (input, operand))
	return input;
      else
	return NULL_TREE;
    }

  if (!res_type)
    {
      if (TREE_CODE_CLASS (opcode) == tcc_comparison)
	res_type = boolean_type_node;
      else if (expr_type_first_operand_type_p (opcode))
	res_type = TREE_TYPE (input);
      else
	return NULL_TREE;
    }

  if (TREE_CODE_CLASS (opcode) == tcc_unary)
    res = fold_unary (opcode, res_type, input);
  else
    res = fold_binary (opcode, res_type, input, operand);

  if (res && !is_gimple_ip_invariant (res))
    return NULL_TREE;

  return res;
}

/* Return the result of a (possibly arithmetic) pass through jump function
   JFUNC on the constant value INPUT.  RES_TYPE is the type of the parameter
   to which the result is passed.  Return NULL_TREE if that cannot be
   determined or be considered an interprocedural invariant.  */

static tree
ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input,
				tree res_type)
{
  return ipa_get_jf_arith_result (ipa_get_jf_pass_through_operation (jfunc),
				  input,
				  ipa_get_jf_pass_through_operand (jfunc),
				  res_type);
}

/* Return the result of an ancestor jump function JFUNC on the constant value
   INPUT.  Return NULL_TREE if that cannot be determined.  */

static tree
ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
{
  gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
  if (TREE_CODE (input) == ADDR_EXPR)
    {
      gcc_checking_assert (is_gimple_ip_invariant_address (input));
      poly_int64 off = ipa_get_jf_ancestor_offset (jfunc);
      if (known_eq (off, 0))
	return input;
      poly_int64 byte_offset = exact_div (off, BITS_PER_UNIT);
      return build1 (ADDR_EXPR, TREE_TYPE (input),
		     fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (input)), input,
				  build_int_cst (ptr_type_node, byte_offset)));
    }
  else
    return NULL_TREE;
}

/* Determine whether JFUNC evaluates to a single known constant value and if
   so, return it.  Otherwise return NULL.  INFO describes the caller node or
   the one it is inlined to, so that pass-through jump functions can be
   evaluated.  PARM_TYPE is the type of the parameter to which the result is
   passed.  */

tree
ipa_value_from_jfunc (class ipa_node_params *info, struct ipa_jump_func *jfunc,
		      tree parm_type)
{
  if (jfunc->type == IPA_JF_CONST)
    return ipa_get_jf_constant (jfunc);
  else if (jfunc->type == IPA_JF_PASS_THROUGH
	   || jfunc->type == IPA_JF_ANCESTOR)
    {
      tree input;
      int idx;

      if (jfunc->type == IPA_JF_PASS_THROUGH)
	idx = ipa_get_jf_pass_through_formal_id (jfunc);
      else
	idx = ipa_get_jf_ancestor_formal_id (jfunc);

      if (info->ipcp_orig_node)
	input = info->known_csts[idx];
      else
	{
	  ipcp_lattice<tree> *lat;

	  if (!info->lattices
	      || idx >= ipa_get_param_count (info))
	    return NULL_TREE;
	  lat = ipa_get_scalar_lat (info, idx);
	  if (!lat->is_single_const ())
	    return NULL_TREE;
	  input = lat->values->value;
	}

      if (!input)
	return NULL_TREE;

      if (jfunc->type == IPA_JF_PASS_THROUGH)
	return ipa_get_jf_pass_through_result (jfunc, input, parm_type);
      else
	return ipa_get_jf_ancestor_result (jfunc, input);
    }
  else
    return NULL_TREE;
}

/* Determine whether JFUNC evaluates to single known polymorphic context, given
   that INFO describes the caller node or the one it is inlined to, CS is the
   call graph edge corresponding to JFUNC and CSIDX index of the described
   parameter.  */

ipa_polymorphic_call_context
ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
			ipa_jump_func *jfunc)
{
  ipa_edge_args *args = ipa_edge_args_sum->get (cs);
  ipa_polymorphic_call_context ctx;
  ipa_polymorphic_call_context *edge_ctx
    = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;

  if (edge_ctx && !edge_ctx->useless_p ())
    ctx = *edge_ctx;

  if (jfunc->type == IPA_JF_PASS_THROUGH
      || jfunc->type == IPA_JF_ANCESTOR)
    {
      ipa_polymorphic_call_context srcctx;
      int srcidx;
      bool type_preserved = true;
      if (jfunc->type == IPA_JF_PASS_THROUGH)
	{
	  if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
	    return ctx;
	  type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
	  srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
	}
      else
	{
	  type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
	  srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
	}
      if (info->ipcp_orig_node)
	{
	  if (info->known_contexts.exists ())
	    srcctx = info->known_contexts[srcidx];
	}
      else
	{
	  if (!info->lattices
	      || srcidx >= ipa_get_param_count (info))
	    return ctx;
	  ipcp_lattice<ipa_polymorphic_call_context> *lat;
	  lat = ipa_get_poly_ctx_lat (info, srcidx);
	  if (!lat->is_single_const ())
	    return ctx;
	  srcctx = lat->values->value;
	}
      if (srcctx.useless_p ())
	return ctx;
      if (jfunc->type == IPA_JF_ANCESTOR)
	srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
      if (!type_preserved)
	srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
      srcctx.combine_with (ctx);
      return srcctx;
    }

  return ctx;
}

/* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
   DST_TYPE on value range in SRC_VR and store it to DST_VR.  Return true if
   the result is a range or an anti-range.  */

static bool
ipa_vr_operation_and_type_effects (value_range *dst_vr,
				   value_range *src_vr,
				   enum tree_code operation,
				   tree dst_type, tree src_type)
{
  range_fold_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
  if (dst_vr->varying_p () || dst_vr->undefined_p ())
    return false;
  return true;
}

/* Determine value_range of JFUNC given that INFO describes the caller node or
   the one it is inlined to, CS is the call graph edge corresponding to JFUNC
   and PARM_TYPE of the parameter.  */

value_range
ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs,
			    ipa_jump_func *jfunc, tree parm_type)
{
  value_range vr;
  return vr;
  if (jfunc->m_vr)
    ipa_vr_operation_and_type_effects (&vr,
				       jfunc->m_vr,
				       NOP_EXPR, parm_type,
				       jfunc->m_vr->type ());
  if (vr.singleton_p ())
    return vr;
  if (jfunc->type == IPA_JF_PASS_THROUGH)
    {
      int idx;
      ipcp_transformation *sum
	= ipcp_get_transformation_summary (cs->caller->inlined_to
					   ? cs->caller->inlined_to
					   : cs->caller);
      if (!sum || !sum->m_vr)
	return vr;

      idx = ipa_get_jf_pass_through_formal_id (jfunc);

      if (!(*sum->m_vr)[idx].known)
	return vr;
      tree vr_type = ipa_get_type (info, idx);
      value_range srcvr (wide_int_to_tree (vr_type, (*sum->m_vr)[idx].min),
			 wide_int_to_tree (vr_type, (*sum->m_vr)[idx].max),
			 (*sum->m_vr)[idx].type);

      enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);

      if (TREE_CODE_CLASS (operation) == tcc_unary)
	{
	  value_range res;

	  if (ipa_vr_operation_and_type_effects (&res,
						 &srcvr,
						 operation, parm_type,
						 vr_type))
	    vr.intersect (res);
	}
      else
	{
	  value_range op_res, res;
	  tree op = ipa_get_jf_pass_through_operand (jfunc);
	  value_range op_vr (op, op);

	  range_fold_binary_expr (&op_res, operation, vr_type, &srcvr, &op_vr);
	  if (ipa_vr_operation_and_type_effects (&res,
						 &op_res,
						 NOP_EXPR, parm_type,
						 vr_type))
	    vr.intersect (res);
	}
    }
  return vr;
}

/* See if NODE is a clone with a known aggregate value at a given OFFSET of a
   parameter with the given INDEX.  */

static tree
get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
		     int index)
{
  struct ipa_agg_replacement_value *aggval;

  aggval = ipa_get_agg_replacements_for_node (node);
  while (aggval)
    {
      if (aggval->offset == offset
	  && aggval->index == index)
	return aggval->value;
      aggval = aggval->next;
    }
  return NULL_TREE;
}

/* Determine whether ITEM, jump function for an aggregate part, evaluates to a
   single known constant value and if so, return it.  Otherwise return NULL.
   NODE and INFO describes the caller node or the one it is inlined to, and
   its related info.  */

static tree
ipa_agg_value_from_node (class ipa_node_params *info,
			 struct cgraph_node *node,
			 struct ipa_agg_jf_item *item)
{
  tree value = NULL_TREE;
  int src_idx;

  if (item->offset < 0 || item->jftype == IPA_JF_UNKNOWN)
    return NULL_TREE;

  if (item->jftype == IPA_JF_CONST)
    return item->value.constant;

  gcc_checking_assert (item->jftype == IPA_JF_PASS_THROUGH
		       || item->jftype == IPA_JF_LOAD_AGG);

  src_idx = item->value.pass_through.formal_id;

  if (info->ipcp_orig_node)
    {
      if (item->jftype == IPA_JF_PASS_THROUGH)
	value = info->known_csts[src_idx];
      else
	value = get_clone_agg_value (node, item->value.load_agg.offset,
				     src_idx);
    }
  else if (info->lattices)
    {
      class ipcp_param_lattices *src_plats
	= ipa_get_parm_lattices (info, src_idx);

      if (item->jftype == IPA_JF_PASS_THROUGH)
	{
	  struct ipcp_lattice<tree> *lat = &src_plats->itself;

	  if (!lat->is_single_const ())
	    return NULL_TREE;

	  value = lat->values->value;
	}
      else if (src_plats->aggs
	       && !src_plats->aggs_bottom
	       && !src_plats->aggs_contain_variable
	       && src_plats->aggs_by_ref == item->value.load_agg.by_ref)
	{
	  struct ipcp_agg_lattice *aglat;

	  for (aglat = src_plats->aggs; aglat; aglat = aglat->next)
	    {
	      if (aglat->offset > item->value.load_agg.offset)
		break;

	      if (aglat->offset == item->value.load_agg.offset)
		{
		  if (aglat->is_single_const ())
		    value = aglat->values->value;
		  break;
		}
	    }
	}
    }

  if (!value)
    return NULL_TREE;

  if (item->jftype == IPA_JF_LOAD_AGG)
    {
      tree load_type = item->value.load_agg.type;
      tree value_type = TREE_TYPE (value);

      /* Ensure value type is compatible with load type.  */
      if (!useless_type_conversion_p (load_type, value_type))
	return NULL_TREE;
    }

  return ipa_get_jf_arith_result (item->value.pass_through.operation,
				  value,
				  item->value.pass_through.operand,
				  item->type);
}

/* Determine whether AGG_JFUNC evaluates to a set of known constant value for
   an aggregate and if so, return it.  Otherwise return an empty set.  NODE
   and INFO describes the caller node or the one it is inlined to, and its
   related info.  */

struct ipa_agg_value_set
ipa_agg_value_set_from_jfunc (class ipa_node_params *info, cgraph_node *node,
			      struct ipa_agg_jump_function *agg_jfunc)
{
  struct ipa_agg_value_set agg;
  struct ipa_agg_jf_item *item;
  int i;

  agg.items = vNULL;
  agg.by_ref = agg_jfunc->by_ref;

  FOR_EACH_VEC_SAFE_ELT (agg_jfunc->items, i, item)
    {
      tree value = ipa_agg_value_from_node (info, node, item);

      if (value)
	{
	  struct ipa_agg_value value_item;

	  value_item.offset = item->offset;
	  value_item.value = value;

	  agg.items.safe_push (value_item);
	}
    }
  return agg;
}

/* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
   bottom, not containing a variable component and without any known value at
   the same time.  */

DEBUG_FUNCTION void
ipcp_verify_propagated_values (void)
{
  struct cgraph_node *node;

  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
    {
      ipa_node_params *info = ipa_node_params_sum->get (node);
      if (!opt_for_fn (node->decl, flag_ipa_cp)
	  || !opt_for_fn (node->decl, optimize))
	continue;
      int i, count = ipa_get_param_count (info);

      for (i = 0; i < count; i++)
	{
	  ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);

	  if (!lat->bottom
	      && !lat->contains_variable
	      && lat->values_count == 0)
	    {
	      if (dump_file)
		{
		  symtab->dump (dump_file);
		  fprintf (dump_file, "\nIPA lattices after constant "
			   "propagation, before gcc_unreachable:\n");
		  print_all_lattices (dump_file, true, false);
		}

	      gcc_unreachable ();
	    }
	}
    }
}

/* Return true iff X and Y should be considered equal contexts by IPA-CP.  */

static bool
values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
			 ipa_polymorphic_call_context y)
{
  return x.equal_to (y);
}


/* Add a new value source to the value represented by THIS, marking that a
   value comes from edge CS and (if the underlying jump function is a
   pass-through or an ancestor one) from a caller value SRC_VAL of a caller
   parameter described by SRC_INDEX.  OFFSET is negative if the source was the
   scalar value of the parameter itself or the offset within an aggregate.  */

template <typename valtype>
void
ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
				 int src_idx, HOST_WIDE_INT offset)
{
  ipcp_value_source<valtype> *src;

  src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
  src->offset = offset;
  src->cs = cs;
  src->val = src_val;
  src->index = src_idx;

  src->next = sources;
  sources = src;
}

/* Allocate a new ipcp_value holding a tree constant, initialize its value to
   SOURCE and clear all other fields.  */

static ipcp_value<tree> *
allocate_and_init_ipcp_value (tree cst, unsigned same_lat_gen_level)
{
  ipcp_value<tree> *val;

  val = new (ipcp_cst_values_pool.allocate ()) ipcp_value<tree>();
  val->value = cst;
  val->self_recursion_generated_level = same_lat_gen_level;
  return val;
}

/* Allocate a new ipcp_value holding a polymorphic context, initialize its
   value to SOURCE and clear all other fields.  */

static ipcp_value<ipa_polymorphic_call_context> *
allocate_and_init_ipcp_value (ipa_polymorphic_call_context ctx,
			      unsigned same_lat_gen_level)
{
  ipcp_value<ipa_polymorphic_call_context> *val;

  val = new (ipcp_poly_ctx_values_pool.allocate ())
    ipcp_value<ipa_polymorphic_call_context>();
  val->value = ctx;
  val->self_recursion_generated_level = same_lat_gen_level;
  return val;
}

/* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it.  CS,
   SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
   meaning.  OFFSET -1 means the source is scalar and not a part of an
   aggregate.  If non-NULL, VAL_P records address of existing or newly added
   ipcp_value.

   If the value is generated for a self-recursive call as a result of an
   arithmetic pass-through jump-function acting on a value in the same lattice,
   SAME_LAT_GEN_LEVEL must be the length of such chain, otherwise it must be
   zero.  If it is non-zero, PARAM_IPA_CP_VALUE_LIST_SIZE limit is ignored.  */

template <typename valtype>
bool
ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
				  ipcp_value<valtype> *src_val,
				  int src_idx, HOST_WIDE_INT offset,
				  ipcp_value<valtype> **val_p,
				  unsigned same_lat_gen_level)
{
  ipcp_value<valtype> *val, *last_val = NULL;

  if (val_p)
    *val_p = NULL;

  if (bottom)
    return false;

  for (val = values; val; last_val = val, val = val->next)
    if (values_equal_for_ipcp_p (val->value, newval))
      {
	if (val_p)
	  *val_p = val;

	if (val->self_recursion_generated_level < same_lat_gen_level)
	  val->self_recursion_generated_level = same_lat_gen_level;

	if (ipa_edge_within_scc (cs))
	  {
	    ipcp_value_source<valtype> *s;
	    for (s = val->sources; s; s = s->next)
	      if (s->cs == cs && s->val == src_val)
		break;
	    if (s)
	      return false;
	  }

	val->add_source (cs, src_val, src_idx, offset);
	return false;
      }

  if (!same_lat_gen_level && values_count == opt_for_fn (cs->caller->decl,
						param_ipa_cp_value_list_size))
    {
      /* We can only free sources, not the values themselves, because sources
	 of other values in this SCC might point to them.   */
      for (val = values; val; val = val->next)
	{
	  while (val->sources)
	    {
	      ipcp_value_source<valtype> *src = val->sources;
	      val->sources = src->next;
	      ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
	    }
	}
      values = NULL;
      return set_to_bottom ();
    }

  values_count++;
  val = allocate_and_init_ipcp_value (newval, same_lat_gen_level);
  val->add_source (cs, src_val, src_idx, offset);
  val->next = NULL;

  /* Add the new value to end of value list, which can reduce iterations
     of propagation stage for recursive function.  */
  if (last_val)
    last_val->next = val;
  else
    values = val;

  if (val_p)
    *val_p = val;

  return true;
}

/* A helper function that returns result of operation specified by OPCODE on
   the value of SRC_VAL.  If non-NULL, OPND1_TYPE is expected type for the
   value of SRC_VAL.  If the operation is binary, OPND2 is a constant value
   acting as its second operand.  If non-NULL, RES_TYPE is expected type of
   the result.  */

static tree
get_val_across_arith_op (enum tree_code opcode,
			 tree opnd1_type,
			 tree opnd2,
			 ipcp_value<tree> *src_val,
			 tree res_type)
{
  tree opnd1 = src_val->value;

  /* Skip source values that is incompatible with specified type.  */
  if (opnd1_type
      && !useless_type_conversion_p (opnd1_type, TREE_TYPE (opnd1)))
    return NULL_TREE;

  return ipa_get_jf_arith_result (opcode, opnd1, opnd2, res_type);
}

/* Propagate values through an arithmetic transformation described by a jump
   function associated with edge CS, taking values from SRC_LAT and putting
   them into DEST_LAT.  OPND1_TYPE is expected type for the values in SRC_LAT.
   OPND2 is a constant value if transformation is a binary operation.
   SRC_OFFSET specifies offset in an aggregate if SRC_LAT describes lattice of
   a part of the aggregate.  SRC_IDX is the index of the source parameter.
   RES_TYPE is the value type of result being propagated into.  Return true if
   DEST_LAT changed.  */

static bool
propagate_vals_across_arith_jfunc (cgraph_edge *cs,
				   enum tree_code opcode,
				   tree opnd1_type,
				   tree opnd2,
				   ipcp_lattice<tree> *src_lat,
				   ipcp_lattice<tree> *dest_lat,
				   HOST_WIDE_INT src_offset,
				   int src_idx,
				   tree res_type)
{
  ipcp_value<tree> *src_val;
  bool ret = false;

  /* Due to circular dependencies, propagating within an SCC through arithmetic
     transformation would create infinite number of values.  But for
     self-feeding recursive function, we could allow propagation in a limited
     count, and this can enable a simple kind of recursive function versioning.
     For other scenario, we would just make lattices bottom.  */
  if (opcode != NOP_EXPR && ipa_edge_within_scc (cs))
    {
      int i;

      int max_recursive_depth = opt_for_fn(cs->caller->decl,
					   param_ipa_cp_max_recursive_depth);
      if (src_lat != dest_lat || max_recursive_depth < 1)
	return dest_lat->set_contains_variable ();

      /* No benefit if recursive execution is in low probability.  */
      if (cs->sreal_frequency () * 100
	  <= ((sreal) 1) * opt_for_fn (cs->caller->decl,
				       param_ipa_cp_min_recursive_probability))
	return dest_lat->set_contains_variable ();

      auto_vec<ipcp_value<tree> *, 8> val_seeds;

      for (src_val = src_lat->values; src_val; src_val = src_val->next)
	{
	  /* Now we do not use self-recursively generated value as propagation
	     source, this is absolutely conservative, but could avoid explosion
	     of lattice's value space, especially when one recursive function
	     calls another recursive.  */
	  if (src_val->self_recursion_generated_p ())
	    {
	      ipcp_value_source<tree> *s;

	      /* If the lattice has already been propagated for the call site,
		 no need to do that again.  */
	      for (s = src_val->sources; s; s = s->next)
		if (s->cs == cs)
		  return dest_lat->set_contains_variable ();
	    }
	  else
	    val_seeds.safe_push (src_val);
	}

      gcc_assert ((int) val_seeds.length () <= param_ipa_cp_value_list_size);

      /* Recursively generate lattice values with a limited count.  */
      FOR_EACH_VEC_ELT (val_seeds, i, src_val)
	{
	  for (int j = 1; j < max_recursive_depth; j++)
	    {
	      tree cstval = get_val_across_arith_op (opcode, opnd1_type, opnd2,
						     src_val, res_type);
	      if (!cstval
		  || !ipacp_value_safe_for_type (res_type, cstval))
		break;

	      ret |= dest_lat->add_value (cstval, cs, src_val, src_idx,
					  src_offset, &src_val, j);
	      gcc_checking_assert (src_val);
	    }
	}
      ret |= dest_lat->set_contains_variable ();
    }
  else
    for (src_val = src_lat->values; src_val; src_val = src_val->next)
      {
	/* Now we do not use self-recursively generated value as propagation
	   source, otherwise it is easy to make value space of normal lattice
	   overflow.  */
	if (src_val->self_recursion_generated_p ())
	  {
	    ret |= dest_lat->set_contains_variable ();
	    continue;
	  }

	tree cstval = get_val_across_arith_op (opcode, opnd1_type, opnd2,
					       src_val, res_type);
	if (cstval
	    && ipacp_value_safe_for_type (res_type, cstval))
	  ret |= dest_lat->add_value (cstval, cs, src_val, src_idx,
				      src_offset);
	else
	  ret |= dest_lat->set_contains_variable ();
      }

  return ret;
}

/* Propagate values through a pass-through jump function JFUNC associated with
   edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
   is the index of the source parameter.  PARM_TYPE is the type of the
   parameter to which the result is passed.  */

static bool
propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc,
				    ipcp_lattice<tree> *src_lat,
				    ipcp_lattice<tree> *dest_lat, int src_idx,
				    tree parm_type)
{
  return propagate_vals_across_arith_jfunc (cs,
				ipa_get_jf_pass_through_operation (jfunc),
				NULL_TREE,
				ipa_get_jf_pass_through_operand (jfunc),
				src_lat, dest_lat, -1, src_idx, parm_type);
}

/* Propagate values through an ancestor jump function JFUNC associated with
   edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
   is the index of the source parameter.  */

static bool
propagate_vals_across_ancestor (struct cgraph_edge *cs,
				struct ipa_jump_func *jfunc,
				ipcp_lattice<tree> *src_lat,
				ipcp_lattice<tree> *dest_lat, int src_idx,
				tree param_type)
{
  ipcp_value<tree> *src_val;
  bool ret = false;

  if (ipa_edge_within_scc (cs))
    return dest_lat->set_contains_variable ();

  for (src_val = src_lat->values; src_val; src_val = src_val->next)
    {
      tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);

      if (t && ipacp_value_safe_for_type (param_type, t))
	ret |= dest_lat->add_value (t, cs, src_val, src_idx);
      else
	ret |= dest_lat->set_contains_variable ();
    }

  return ret;
}

/* Propagate scalar values across jump function JFUNC that is associated with
   edge CS and put the values into DEST_LAT.  PARM_TYPE is the type of the
   parameter to which the result is passed.  */

static bool
propagate_scalar_across_jump_function (struct cgraph_edge *cs,
				       struct ipa_jump_func *jfunc,
				       ipcp_lattice<tree> *dest_lat,
				       tree param_type)
{
  if (dest_lat->bottom)
    return false;

  if (jfunc->type == IPA_JF_CONST)
    {
      tree val = ipa_get_jf_constant (jfunc);
      if (ipacp_value_safe_for_type (param_type, val))
	return dest_lat->add_value (val, cs, NULL, 0);
      else
	return dest_lat->set_contains_variable ();
    }
  else if (jfunc->type == IPA_JF_PASS_THROUGH
	   || jfunc->type == IPA_JF_ANCESTOR)
    {
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      ipcp_lattice<tree> *src_lat;
      int src_idx;
      bool ret;

      if (jfunc->type == IPA_JF_PASS_THROUGH)
	src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
      else
	src_idx = ipa_get_jf_ancestor_formal_id (jfunc);

      src_lat = ipa_get_scalar_lat (caller_info, src_idx);
      if (src_lat->bottom)
	return dest_lat->set_contains_variable ();

      /* If we would need to clone the caller and cannot, do not propagate.  */
      if (!ipcp_versionable_function_p (cs->caller)
	  && (src_lat->contains_variable
	      || (src_lat->values_count > 1)))
	return dest_lat->set_contains_variable ();

      if (jfunc->type == IPA_JF_PASS_THROUGH)
	ret = propagate_vals_across_pass_through (cs, jfunc, src_lat,
						  dest_lat, src_idx,
						  param_type);
      else
	ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat,
					      src_idx, param_type);

      if (src_lat->contains_variable)
	ret |= dest_lat->set_contains_variable ();

      return ret;
    }

  /* TODO: We currently do not handle member method pointers in IPA-CP (we only
     use it for indirect inlining), we should propagate them too.  */
  return dest_lat->set_contains_variable ();
}

/* Propagate scalar values across jump function JFUNC that is associated with
   edge CS and describes argument IDX and put the values into DEST_LAT.  */

static bool
propagate_context_across_jump_function (cgraph_edge *cs,
			  ipa_jump_func *jfunc, int idx,
			  ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
{
  if (dest_lat->bottom)
    return false;
  ipa_edge_args *args = ipa_edge_args_sum->get (cs);
  bool ret = false;
  bool added_sth = false;
  bool type_preserved = true;

  ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
    = ipa_get_ith_polymorhic_call_context (args, idx);

  if (edge_ctx_ptr)
    edge_ctx = *edge_ctx_ptr;

  if (jfunc->type == IPA_JF_PASS_THROUGH
      || jfunc->type == IPA_JF_ANCESTOR)
    {
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      int src_idx;
      ipcp_lattice<ipa_polymorphic_call_context> *src_lat;

      /* TODO: Once we figure out how to propagate speculations, it will
	 probably be a good idea to switch to speculation if type_preserved is
	 not set instead of punting.  */
      if (jfunc->type == IPA_JF_PASS_THROUGH)
	{
	  if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
	    goto prop_fail;
	  type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
	  src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
	}
      else
	{
	  type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
	  src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
	}

      src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
      /* If we would need to clone the caller and cannot, do not propagate.  */
      if (!ipcp_versionable_function_p (cs->caller)
	  && (src_lat->contains_variable
	      || (src_lat->values_count > 1)))
	goto prop_fail;

      ipcp_value<ipa_polymorphic_call_context> *src_val;
      for (src_val = src_lat->values; src_val; src_val = src_val->next)
	{
	  ipa_polymorphic_call_context cur = src_val->value;

	  if (!type_preserved)
	    cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
	  if (jfunc->type == IPA_JF_ANCESTOR)
	    cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
	  /* TODO: In cases we know how the context is going to be used,
	     we can improve the result by passing proper OTR_TYPE.  */
	  cur.combine_with (edge_ctx);
	  if (!cur.useless_p ())
	    {
	      if (src_lat->contains_variable
		  && !edge_ctx.equal_to (cur))
		ret |= dest_lat->set_contains_variable ();
	      ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
	      added_sth = true;
	    }
	}
    }

 prop_fail:
  if (!added_sth)
    {
      if (!edge_ctx.useless_p ())
	ret |= dest_lat->add_value (edge_ctx, cs);
      else
	ret |= dest_lat->set_contains_variable ();
    }

  return ret;
}

/* Propagate bits across jfunc that is associated with
   edge cs and update dest_lattice accordingly.  */

bool
propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
				     ipa_jump_func *jfunc,
				     ipcp_bits_lattice *dest_lattice)
{
  if (dest_lattice->bottom_p ())
    return false;

  enum availability availability;
  cgraph_node *callee = cs->callee->function_symbol (&availability);
  ipa_node_params *callee_info = ipa_node_params_sum->get (callee);
  tree parm_type = ipa_get_type (callee_info, idx);

  /* For K&R C programs, ipa_get_type() could return NULL_TREE.  Avoid the
     transform for these cases.  Similarly, we can have bad type mismatches
     with LTO, avoid doing anything with those too.  */
  if (!parm_type
      || (!INTEGRAL_TYPE_P (parm_type) && !POINTER_TYPE_P (parm_type)))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "Setting dest_lattice to bottom, because type of "
		 "param %i of %s is NULL or unsuitable for bits propagation\n",
		 idx, cs->callee->dump_name ());

      return dest_lattice->set_to_bottom ();
    }

  unsigned precision = TYPE_PRECISION (parm_type);
  signop sgn = TYPE_SIGN (parm_type);

  if (jfunc->type == IPA_JF_PASS_THROUGH
      || jfunc->type == IPA_JF_ANCESTOR)
    {
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      tree operand = NULL_TREE;
      enum tree_code code;
      unsigned src_idx;

      if (jfunc->type == IPA_JF_PASS_THROUGH)
	{
	  code = ipa_get_jf_pass_through_operation (jfunc);
	  src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
	  if (code != NOP_EXPR)
	    operand = ipa_get_jf_pass_through_operand (jfunc);
	}
      else
	{
	  code = POINTER_PLUS_EXPR;
	  src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
	  unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
	  operand = build_int_cstu (size_type_node, offset);
	}

      class ipcp_param_lattices *src_lats
	= ipa_get_parm_lattices (caller_info, src_idx);

      /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
	 for eg consider:
	 int f(int x)
	 {
	   g (x & 0xff);
	 }
	 Assume lattice for x is bottom, however we can still propagate
	 result of x & 0xff == 0xff, which gets computed during ccp1 pass
	 and we store it in jump function during analysis stage.  */

      if (src_lats->bits_lattice.bottom_p ()
	  && jfunc->bits)
	return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
					precision);
      else
	return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn,
					code, operand);
    }

  else if (jfunc->type == IPA_JF_ANCESTOR)
    return dest_lattice->set_to_bottom ();
  else if (jfunc->bits)
    return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
				    precision);
  else
    return dest_lattice->set_to_bottom ();
}

/* Propagate value range across jump function JFUNC that is associated with
   edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
   accordingly.  */

static bool
propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
				   class ipcp_param_lattices *dest_plats,
				   tree param_type)
{
  ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;

  if (dest_lat->bottom_p ())
    return false;

  if (!param_type
      || (!INTEGRAL_TYPE_P (param_type)
	  && !POINTER_TYPE_P (param_type)))
    return dest_lat->set_to_bottom ();

  if (jfunc->type == IPA_JF_PASS_THROUGH)
    {
      enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
      class ipcp_param_lattices *src_lats
	= ipa_get_parm_lattices (caller_info, src_idx);
      tree operand_type = ipa_get_type (caller_info, src_idx);

      if (src_lats->m_value_range.bottom_p ())
	return dest_lat->set_to_bottom ();

      value_range vr;
      if (TREE_CODE_CLASS (operation) == tcc_unary)
	ipa_vr_operation_and_type_effects (&vr,
					   &src_lats->m_value_range.m_vr,
					   operation, param_type,
					   operand_type);
      /* A crude way to prevent unbounded number of value range updates
	 in SCC components.  We should allow limited number of updates within
	 SCC, too.  */
      else if (!ipa_edge_within_scc (cs))
	{
	  tree op = ipa_get_jf_pass_through_operand (jfunc);
	  value_range op_vr (op, op);
	  value_range op_res,res;

	  range_fold_binary_expr (&op_res, operation, operand_type,
				  &src_lats->m_value_range.m_vr, &op_vr);
	  ipa_vr_operation_and_type_effects (&vr,
					     &op_res,
					     NOP_EXPR, param_type,
					     operand_type);
	}
      if (!vr.undefined_p () && !vr.varying_p ())
	{
	  if (jfunc->m_vr)
	    {
	      value_range jvr;
	      if (ipa_vr_operation_and_type_effects (&jvr, jfunc->m_vr,
						     NOP_EXPR,
						     param_type,
						     jfunc->m_vr->type ()))
		vr.intersect (jvr);
	    }
	  return dest_lat->meet_with (&vr);
	}
    }
  else if (jfunc->type == IPA_JF_CONST)
    {
      tree val = ipa_get_jf_constant (jfunc);
      if (TREE_CODE (val) == INTEGER_CST)
	{
	  val = fold_convert (param_type, val);
	  if (TREE_OVERFLOW_P (val))
	    val = drop_tree_overflow (val);

	  value_range tmpvr (val, val);
	  return dest_lat->meet_with (&tmpvr);
	}
    }

  value_range vr;
  if (jfunc->m_vr
      && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
					    param_type,
					    jfunc->m_vr->type ()))
    return dest_lat->meet_with (&vr);
  else
    return dest_lat->set_to_bottom ();
}

/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
   NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
   other cases, return false).  If there are no aggregate items, set
   aggs_by_ref to NEW_AGGS_BY_REF.  */

static bool
set_check_aggs_by_ref (class ipcp_param_lattices *dest_plats,
		       bool new_aggs_by_ref)
{
  if (dest_plats->aggs)
    {
      if (dest_plats->aggs_by_ref != new_aggs_by_ref)
	{
	  set_agg_lats_to_bottom (dest_plats);
	  return true;
	}
    }
  else
    dest_plats->aggs_by_ref = new_aggs_by_ref;
  return false;
}

/* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
   already existing lattice for the given OFFSET and SIZE, marking all skipped
   lattices as containing variable and checking for overlaps.  If there is no
   already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
   it with offset, size and contains_variable to PRE_EXISTING, and return true,
   unless there are too many already.  If there are two many, return false.  If
   there are overlaps turn whole DEST_PLATS to bottom and return false.  If any
   skipped lattices were newly marked as containing variable, set *CHANGE to
   true.  MAX_AGG_ITEMS is the maximum number of lattices.  */

static bool
merge_agg_lats_step (class ipcp_param_lattices *dest_plats,
		     HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
		     struct ipcp_agg_lattice ***aglat,
		     bool pre_existing, bool *change, int max_agg_items)
{
  gcc_checking_assert (offset >= 0);

  while (**aglat && (**aglat)->offset < offset)
    {
      if ((**aglat)->offset + (**aglat)->size > offset)
	{
	  set_agg_lats_to_bottom (dest_plats);
	  return false;
	}
      *change |= (**aglat)->set_contains_variable ();
      *aglat = &(**aglat)->next;
    }

  if (**aglat && (**aglat)->offset == offset)
    {
      if ((**aglat)->size != val_size)
	{
	  set_agg_lats_to_bottom (dest_plats);
	  return false;
	}
      gcc_assert (!(**aglat)->next
		  || (**aglat)->next->offset >= offset + val_size);
      return true;
    }
  else
    {
      struct ipcp_agg_lattice *new_al;

      if (**aglat && (**aglat)->offset < offset + val_size)
	{
	  set_agg_lats_to_bottom (dest_plats);
	  return false;
	}
      if (dest_plats->aggs_count == max_agg_items)
	return false;
      dest_plats->aggs_count++;
      new_al = ipcp_agg_lattice_pool.allocate ();
      memset (new_al, 0, sizeof (*new_al));

      new_al->offset = offset;
      new_al->size = val_size;
      new_al->contains_variable = pre_existing;

      new_al->next = **aglat;
      **aglat = new_al;
      return true;
    }
}

/* Set all AGLAT and all other aggregate lattices reachable by next pointers as
   containing an unknown value.  */

static bool
set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
{
  bool ret = false;
  while (aglat)
    {
      ret |= aglat->set_contains_variable ();
      aglat = aglat->next;
    }
  return ret;
}

/* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
   DELTA_OFFSET.  CS is the call graph edge and SRC_IDX the index of the source
   parameter used for lattice value sources.  Return true if DEST_PLATS changed
   in any way.  */

static bool
merge_aggregate_lattices (struct cgraph_edge *cs,
			  class ipcp_param_lattices *dest_plats,
			  class ipcp_param_lattices *src_plats,
			  int src_idx, HOST_WIDE_INT offset_delta)
{
  bool pre_existing = dest_plats->aggs != NULL;
  struct ipcp_agg_lattice **dst_aglat;
  bool ret = false;

  if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
    return true;
  if (src_plats->aggs_bottom)
    return set_agg_lats_contain_variable (dest_plats);
  if (src_plats->aggs_contain_variable)
    ret |= set_agg_lats_contain_variable (dest_plats);
  dst_aglat = &dest_plats->aggs;

  int max_agg_items = opt_for_fn (cs->callee->function_symbol ()->decl,
				  param_ipa_max_agg_items);
  for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
       src_aglat;
       src_aglat = src_aglat->next)
    {
      HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;

      if (new_offset < 0)
	continue;
      if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
			       &dst_aglat, pre_existing, &ret, max_agg_items))
	{
	  struct ipcp_agg_lattice *new_al = *dst_aglat;

	  dst_aglat = &(*dst_aglat)->next;
	  if (src_aglat->bottom)
	    {
	      ret |= new_al->set_contains_variable ();
	      continue;
	    }
	  if (src_aglat->contains_variable)
	    ret |= new_al->set_contains_variable ();
	  for (ipcp_value<tree> *val = src_aglat->values;
	       val;
	       val = val->next)
	    ret |= new_al->add_value (val->value, cs, val, src_idx,
				      src_aglat->offset);
	}
      else if (dest_plats->aggs_bottom)
	return true;
    }
  ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
  return ret;
}

/* Determine whether there is anything to propagate FROM SRC_PLATS through a
   pass-through JFUNC and if so, whether it has conform and conforms to the
   rules about propagating values passed by reference.  */

static bool
agg_pass_through_permissible_p (class ipcp_param_lattices *src_plats,
				struct ipa_jump_func *jfunc)
{
  return src_plats->aggs
    && (!src_plats->aggs_by_ref
	|| ipa_get_jf_pass_through_agg_preserved (jfunc));
}

/* Propagate values through ITEM, jump function for a part of an aggregate,
   into corresponding aggregate lattice AGLAT.  CS is the call graph edge
   associated with the jump function.  Return true if AGLAT changed in any
   way.  */

static bool
propagate_aggregate_lattice (struct cgraph_edge *cs,
			     struct ipa_agg_jf_item *item,
			     struct ipcp_agg_lattice *aglat)
{
  class ipa_node_params *caller_info;
  class ipcp_param_lattices *src_plats;
  struct ipcp_lattice<tree> *src_lat;
  HOST_WIDE_INT src_offset;
  int src_idx;
  tree load_type;
  bool ret;

  if (item->jftype == IPA_JF_CONST)
    {
      tree value = item->value.constant;

      gcc_checking_assert (is_gimple_ip_invariant (value));
      return aglat->add_value (value, cs, NULL, 0);
    }

  gcc_checking_assert (item->jftype == IPA_JF_PASS_THROUGH
		       || item->jftype == IPA_JF_LOAD_AGG);

  caller_info = ipa_node_params_sum->get (cs->caller);
  src_idx = item->value.pass_through.formal_id;
  src_plats = ipa_get_parm_lattices (caller_info, src_idx);

  if (item->jftype == IPA_JF_PASS_THROUGH)
    {
      load_type = NULL_TREE;
      src_lat = &src_plats->itself;
      src_offset = -1;
    }
  else
    {
      HOST_WIDE_INT load_offset = item->value.load_agg.offset;
      struct ipcp_agg_lattice *src_aglat;

      for (src_aglat = src_plats->aggs; src_aglat; src_aglat = src_aglat->next)
	if (src_aglat->offset >= load_offset)
	  break;

      load_type = item->value.load_agg.type;
      if (!src_aglat
	  || src_aglat->offset > load_offset
	  || src_aglat->size != tree_to_shwi (TYPE_SIZE (load_type))
	  || src_plats->aggs_by_ref != item->value.load_agg.by_ref)
	return aglat->set_contains_variable ();

      src_lat = src_aglat;
      src_offset = load_offset;
    }

  if (src_lat->bottom
      || (!ipcp_versionable_function_p (cs->caller)
	  && !src_lat->is_single_const ()))
    return aglat->set_contains_variable ();

  ret = propagate_vals_across_arith_jfunc (cs,
					   item->value.pass_through.operation,
					   load_type,
					   item->value.pass_through.operand,
					   src_lat, aglat,
					   src_offset,
					   src_idx,
					   item->type);

  if (src_lat->contains_variable)
    ret |= aglat->set_contains_variable ();

  return ret;
}

/* Propagate scalar values across jump function JFUNC that is associated with
   edge CS and put the values into DEST_LAT.  */

static bool
propagate_aggs_across_jump_function (struct cgraph_edge *cs,
				     struct ipa_jump_func *jfunc,
				     class ipcp_param_lattices *dest_plats)
{
  bool ret = false;

  if (dest_plats->aggs_bottom)
    return false;

  if (jfunc->type == IPA_JF_PASS_THROUGH
      && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
    {
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
      class ipcp_param_lattices *src_plats;

      src_plats = ipa_get_parm_lattices (caller_info, src_idx);
      if (agg_pass_through_permissible_p (src_plats, jfunc))
	{
	  /* Currently we do not produce clobber aggregate jump
	     functions, replace with merging when we do.  */
	  gcc_assert (!jfunc->agg.items);
	  ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
					   src_idx, 0);
	  return ret;
	}
    }
  else if (jfunc->type == IPA_JF_ANCESTOR
	   && ipa_get_jf_ancestor_agg_preserved (jfunc))
    {
      ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller);
      int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
      class ipcp_param_lattices *src_plats;

      src_plats = ipa_get_parm_lattices (caller_info, src_idx);
      if (src_plats->aggs && src_plats->aggs_by_ref)
	{
	  /* Currently we do not produce clobber aggregate jump
	     functions, replace with merging when we do.  */
	  gcc_assert (!jfunc->agg.items);
	  ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
					   ipa_get_jf_ancestor_offset (jfunc));
	}
      else if (!src_plats->aggs_by_ref)
	ret |= set_agg_lats_to_bottom (dest_plats);
      else
	ret |= set_agg_lats_contain_variable (dest_plats);
      return ret;
    }

  if (jfunc->agg.items)
    {
      bool pre_existing = dest_plats->aggs != NULL;
      struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
      struct ipa_agg_jf_item *item;
      int i;

      if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
	return true;

      int max_agg_items = opt_for_fn (cs->callee->function_symbol ()->decl,
				      param_ipa_max_agg_items);
      FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
	{
	  HOST_WIDE_INT val_size;

	  if (item->offset < 0 || item->jftype == IPA_JF_UNKNOWN)
	    continue;
	  val_size = tree_to_shwi (TYPE_SIZE (item->type));

	  if (merge_agg_lats_step (dest_plats, item->offset, val_size,
				   &aglat, pre_existing, &ret, max_agg_items))
	    {
	      ret |= propagate_aggregate_lattice (cs, item, *aglat);
	      aglat = &(*aglat)->next;
	    }
	  else if (dest_plats->aggs_bottom)
	    return true;
	}

      ret |= set_chain_of_aglats_contains_variable (*aglat);
    }
  else
    ret |= set_agg_lats_contain_variable (dest_plats);

  return ret;
}

/* Return true if on the way cfrom CS->caller to the final (non-alias and
   non-thunk) destination, the call passes through a thunk.  */

static bool
call_passes_through_thunk (cgraph_edge *cs)
{
  cgraph_node *alias_or_thunk = cs->callee;
  while (alias_or_thunk->alias)
    alias_or_thunk = alias_or_thunk->get_alias_target ();
  return alias_or_thunk->thunk;
}

/* Propagate constants from the caller to the callee of CS.  INFO describes the
   caller.  */

static bool
propagate_constants_across_call (struct cgraph_edge *cs)
{
  class ipa_node_params *callee_info;
  enum availability availability;
  cgraph_node *callee;
  class ipa_edge_args *args;
  bool ret = false;
  int i, args_count, parms_count;

  callee = cs->callee->function_symbol (&availability);
  if (!callee->definition)
    return false;
  gcc_checking_assert (callee->has_gimple_body_p ());
  callee_info = ipa_node_params_sum->get (callee);
  if (!callee_info)
    return false;

  args = ipa_edge_args_sum->get (cs);
  parms_count = ipa_get_param_count (callee_info);
  if (parms_count == 0)
    return false;
  if (!args
      || !opt_for_fn (cs->caller->decl, flag_ipa_cp)
      || !opt_for_fn (cs->caller->decl, optimize))
    {
      for (i = 0; i < parms_count; i++)
	ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
								 i));
      return ret;
    }
  args_count = ipa_get_cs_argument_count (args);

  /* If this call goes through a thunk we must not propagate to the first (0th)
     parameter.  However, we might need to uncover a thunk from below a series
     of aliases first.  */
  if (call_passes_through_thunk (cs))
    {
      ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
							       0));
      i = 1;
    }
  else
    i = 0;

  for (; (i < args_count) && (i < parms_count); i++)
    {
      struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
      class ipcp_param_lattices *dest_plats;
      tree param_type = ipa_get_type (callee_info, i);

      dest_plats = ipa_get_parm_lattices (callee_info, i);
      if (availability == AVAIL_INTERPOSABLE)
	ret |= set_all_contains_variable (dest_plats);
      else
	{
	  ret |= propagate_scalar_across_jump_function (cs, jump_func,
							&dest_plats->itself,
							param_type);
	  ret |= propagate_context_across_jump_function (cs, jump_func, i,
							 &dest_plats->ctxlat);
	  ret
	    |= propagate_bits_across_jump_function (cs, i, jump_func,
						    &dest_plats->bits_lattice);
	  ret |= propagate_aggs_across_jump_function (cs, jump_func,
						      dest_plats);
	  if (opt_for_fn (callee->decl, flag_ipa_vrp))
	    ret |= propagate_vr_across_jump_function (cs, jump_func,
						      dest_plats, param_type);
	  else
	    ret |= dest_plats->m_value_range.set_to_bottom ();
	}
    }
  for (; i < parms_count; i++)
    ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));

  return ret;
}

/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
   KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination.  The latter
   three can be NULL.  If AGG_REPS is not NULL, KNOWN_AGGS is ignored.  */

static tree
ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
				const vec<tree> &known_csts,
				const vec<ipa_polymorphic_call_context> &known_contexts,
				const vec<ipa_agg_value_set> &known_aggs,
				struct ipa_agg_replacement_value *agg_reps,
				bool *speculative)
{
  int param_index = ie->indirect_info->param_index;
  HOST_WIDE_INT anc_offset;
  tree t = NULL;
  tree target = NULL;

  *speculative = false;

  if (param_index == -1)
    return NULL_TREE;

  if (!ie->indirect_info->polymorphic)
    {
      tree t = NULL;

      if (ie->indirect_info->agg_contents)
	{
	  t = NULL;
	  if (agg_reps && ie->indirect_info->guaranteed_unmodified)
	    {
	      while (agg_reps)
		{
		  if (agg_reps->index == param_index
		      && agg_reps->offset == ie->indirect_info->offset
		      && agg_reps->by_ref == ie->indirect_info->by_ref)
		    {
		      t = agg_reps->value;
		      break;
		    }
		  agg_reps = agg_reps->next;
		}
	    }
	  if (!t)
	    {
	      const ipa_agg_value_set *agg;
	      if (known_aggs.length () > (unsigned int) param_index)
		agg = &known_aggs[param_index];
	      else
		agg = NULL;
	      bool from_global_constant;
	      t = ipa_find_agg_cst_for_param (agg,
					      (unsigned) param_index
						 < known_csts.length ()
					      ? known_csts[param_index]
					      : NULL,
					      ie->indirect_info->offset,
					      ie->indirect_info->by_ref,
					      &from_global_constant);
	      if (t
		  && !from_global_constant
		  && !ie->indirect_info->guaranteed_unmodified)
		t = NULL_TREE;
	    }
	}
      else if ((unsigned) param_index < known_csts.length ())
	t = known_csts[param_index];

      if (t
	  && TREE_CODE (t) == ADDR_EXPR
	  && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
	return TREE_OPERAND (t, 0);
      else
	return NULL_TREE;
    }

  if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
    return NULL_TREE;

  gcc_assert (!ie->indirect_info->agg_contents);
  anc_offset = ie->indirect_info->offset;

  t = NULL;

  /* Try to work out value of virtual table pointer value in replacements.  */
  if (!t && agg_reps && !ie->indirect_info->by_ref)
    {
      while (agg_reps)
	{
	  if (agg_reps->index == param_index
	      && agg_reps->offset == ie->indirect_info->offset
	      && agg_reps->by_ref)
	    {
	      t = agg_reps->value;
	      break;
	    }
	  agg_reps = agg_reps->next;
	}
    }

  /* Try to work out value of virtual table pointer value in known
     aggregate values.  */
  if (!t && known_aggs.length () > (unsigned int) param_index
      && !ie->indirect_info->by_ref)
    {
      const ipa_agg_value_set *agg = &known_aggs[param_index];
      t = ipa_find_agg_cst_for_param (agg,
				      (unsigned) param_index
					 < known_csts.length ()
				      ? known_csts[param_index] : NULL,
				      ie->indirect_info->offset, true);
    }

  /* If we found the virtual table pointer, lookup the target.  */
  if (t)
    {
      tree vtable;
      unsigned HOST_WIDE_INT offset;
      if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
	{
	  bool can_refer;
	  target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
						      vtable, offset, &can_refer);
	  if (can_refer)
	    {
	      if (!target
		  || fndecl_built_in_p (target, BUILT_IN_UNREACHABLE)
		  || !possible_polymorphic_call_target_p
		       (ie, cgraph_node::get (target)))
		{
		  /* Do not speculate builtin_unreachable, it is stupid!  */
		  if (ie->indirect_info->vptr_changed)
		    return NULL;
		  target = ipa_impossible_devirt_target (ie, target);
		}
	      *speculative = ie->indirect_info->vptr_changed;
	      if (!*speculative)
		return target;
	    }
	}
    }

  /* Do we know the constant value of pointer?  */
  if (!t && (unsigned) param_index < known_csts.length ())
    t = known_csts[param_index];

  gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);

  ipa_polymorphic_call_context context;
  if (known_contexts.length () > (unsigned int) param_index)
    {
      context = known_contexts[param_index];
      context.offset_by (anc_offset);
      if (ie->indirect_info->vptr_changed)
	context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
					      ie->indirect_info->otr_type);
      if (t)
	{
	  ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
	    (t, ie->indirect_info->otr_type, anc_offset);
	  if (!ctx2.useless_p ())
	    context.combine_with (ctx2, ie->indirect_info->otr_type);
	}
    }
  else if (t)
    {
      context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
					      anc_offset);
      if (ie->indirect_info->vptr_changed)
	context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
					      ie->indirect_info->otr_type);
    }
  else
    return NULL_TREE;

  vec <cgraph_node *>targets;
  bool final;

  targets = possible_polymorphic_call_targets
    (ie->indirect_info->otr_type,
     ie->indirect_info->otr_token,
     context, &final);
  if (!final || targets.length () > 1)
    {
      struct cgraph_node *node;
      if (*speculative)
	return target;
      if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
	  || ie->speculative || !ie->maybe_hot_p ())
	return NULL;
      node = try_speculative_devirtualization (ie->indirect_info->otr_type,
					       ie->indirect_info->otr_token,
					       context);
      if (node)
	{
	  *speculative = true;
	  target = node->decl;
	}
      else
	return NULL;
    }
  else
    {
      *speculative = false;
      if (targets.length () == 1)
	target = targets[0]->decl;
      else
	target = ipa_impossible_devirt_target (ie, NULL_TREE);
    }

  if (target && !possible_polymorphic_call_target_p (ie,
						     cgraph_node::get (target)))
    {
      if (*speculative)
	return NULL;
      target = ipa_impossible_devirt_target (ie, target);
    }

  return target;
}

/* If an indirect edge IE can be turned into a direct one based on data in
   AVALS, return the destination.  Store into *SPECULATIVE a boolean determinig
   whether the discovered target is only speculative guess.  */

tree
ipa_get_indirect_edge_target (struct cgraph_edge *ie,
			      ipa_call_arg_values *avals,
			      bool *speculative)
{
  return ipa_get_indirect_edge_target_1 (ie, avals->m_known_vals,
					 avals->m_known_contexts,
					 avals->m_known_aggs,
					 NULL, speculative);
}

/* The same functionality as above overloaded for ipa_auto_call_arg_values.  */

tree
ipa_get_indirect_edge_target (struct cgraph_edge *ie,
			      ipa_auto_call_arg_values *avals,
			      bool *speculative)
{
  return ipa_get_indirect_edge_target_1 (ie, avals->m_known_vals,
					 avals->m_known_contexts,
					 avals->m_known_aggs,
					 NULL, speculative);
}

/* Calculate devirtualization time bonus for NODE, assuming we know information
   about arguments stored in AVALS.  */

static int
devirtualization_time_bonus (struct cgraph_node *node,
			     ipa_auto_call_arg_values *avals)
{
  struct cgraph_edge *ie;
  int res = 0;

  for (ie = node->indirect_calls; ie; ie = ie->next_callee)
    {
      struct cgraph_node *callee;
      class ipa_fn_summary *isummary;
      enum availability avail;
      tree target;
      bool speculative;

      target = ipa_get_indirect_edge_target (ie, avals, &speculative);
      if (!target)
	continue;

      /* Only bare minimum benefit for clearly un-inlineable targets.  */
      res += 1;
      callee = cgraph_node::get (target);
      if (!callee || !callee->definition)
	continue;
      callee = callee->function_symbol (&avail);
      if (avail < AVAIL_AVAILABLE)
	continue;
      isummary = ipa_fn_summaries->get (callee);
      if (!isummary || !isummary->inlinable)
	continue;

      int size = ipa_size_summaries->get (callee)->size;
      /* FIXME: The values below need re-considering and perhaps also
	 integrating into the cost metrics, at lest in some very basic way.  */
      int max_inline_insns_auto
	= opt_for_fn (callee->decl, param_max_inline_insns_auto);
      if (size <= max_inline_insns_auto / 4)