gcc/ipa-predicate.c

/* IPA predicates.
   Copyright (C) 2003-2019 Free Software Foundation, Inc.
   Contributed by Jan Hubicka

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "cgraph.h"
#include "tree-vrp.h"
#include "symbol-summary.h"
#include "alloc-pool.h"
#include "ipa-prop.h"
#include "ipa-fnsummary.h"
#include "real.h"
#include "fold-const.h"
#include "tree-pretty-print.h"
#include "gimple.h"
#include "data-streamer.h"


/* Add clause CLAUSE into the predicate P.
   When CONDITIONS is NULL do not perform checking whether NEW_CLAUSE
   is obviously true.  This is useful only when NEW_CLAUSE is known to be
   sane.  */

void
predicate::add_clause (conditions conditions, clause_t new_clause)
{
  int i;
  int i2;
  int insert_here = -1;
  int c1, c2;

  /* True clause.  */
  if (!new_clause)
    return;

  /* False clause makes the whole predicate false.  Kill the other variants.  */
  if (new_clause == (1 << predicate::false_condition))
    {
      *this = false;
      return;
    }
  if (*this == false)
    return;

  /* No one should be silly enough to add false into nontrivial clauses.  */
  gcc_checking_assert (!(new_clause & (1 << predicate::false_condition)));

  /* Look where to insert the new_clause.  At the same time prune out
     new_clauses of P that are implied by the new new_clause and thus
     redundant.  */
  for (i = 0, i2 = 0; i <= max_clauses; i++)
    {
      m_clause[i2] = m_clause[i];

      if (!m_clause[i])
	break;

      /* If m_clause[i] implies new_clause, there is nothing to add.  */
      if ((m_clause[i] & new_clause) == m_clause[i])
	{
	  /* We had nothing to add, none of clauses should've become
	     redundant.  */
	  gcc_checking_assert (i == i2);
	  return;
	}

      if (m_clause[i] < new_clause && insert_here < 0)
	insert_here = i2;

      /* If new_clause implies clause[i], then clause[i] becomes redundant.
         Otherwise the clause[i] has to stay.  */
      if ((m_clause[i] & new_clause) != new_clause)
	i2++;
    }

  /* Look for clauses that are obviously true.  I.e.
     op0 == 5 || op0 != 5.  */
  if (conditions)
    for (c1 = predicate::first_dynamic_condition;
	 c1 < num_conditions; c1++)
      {
	condition *cc1;
	if (!(new_clause & (1 << c1)))
	  continue;
	cc1 = &(*conditions)[c1 - predicate::first_dynamic_condition];
	/* We have no way to represent !changed and !is_not_constant
	   and thus there is no point for looking for them.  */
	if (cc1->code == changed || cc1->code == is_not_constant)
	  continue;
	for (c2 = c1 + 1; c2 < num_conditions; c2++)
	  if (new_clause & (1 << c2))
	    {
	      condition *cc1 =
		&(*conditions)[c1 - predicate::first_dynamic_condition];
	      condition *cc2 =
		&(*conditions)[c2 - predicate::first_dynamic_condition];
	      if (cc1->operand_num == cc2->operand_num
		  && cc1->val == cc2->val
		  && cc2->code != is_not_constant
		  && cc2->code != predicate::changed
		  && cc1->code == invert_tree_comparison (cc2->code,
							  HONOR_NANS (cc1->val)))
		return;
	    }
      }


  /* We run out of variants.  Be conservative in positive direction.  */
  if (i2 == max_clauses)
    return;
  /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
  m_clause[i2 + 1] = 0;
  if (insert_here >= 0)
    for (; i2 > insert_here; i2--)
      m_clause[i2] = m_clause[i2 - 1];
  else
    insert_here = i2;
  m_clause[insert_here] = new_clause;
}


/* Do THIS &= P.  */

predicate &
predicate::operator &= (const predicate &p)
{
  /* Avoid busy work.  */
  if (p == false || *this == true)
    {
      *this = p;
      return *this;
    }
  if (*this == false || p == true || this == &p)
    return *this;

  int i;

  /* See how far predicates match.  */
  for (i = 0; m_clause[i] && m_clause[i] == p.m_clause[i]; i++)
    {
      gcc_checking_assert (i < max_clauses);
    }

  /* Combine the predicates rest.  */
  for (; p.m_clause[i]; i++)
    {
      gcc_checking_assert (i < max_clauses);
      add_clause (NULL, p.m_clause[i]);
    }
  return *this;
}



/* Return THIS | P2.  */

predicate
predicate::or_with (conditions conditions,
	            const predicate &p) const
{
  /* Avoid busy work.  */
  if (p == false || *this == true || *this == p)
    return *this;
  if (*this == false || p == true)
    return p;

  /* OK, combine the predicates.  */
  predicate out = true;

  for (int i = 0; m_clause[i]; i++)
    for (int j = 0; p.m_clause[j]; j++)
      {
	gcc_checking_assert (i < max_clauses && j < max_clauses);
	out.add_clause (conditions, m_clause[i] | p.m_clause[j]);
      }
  return out;
}


/* Having partial truth assignment in POSSIBLE_TRUTHS, return false
   if predicate P is known to be false.  */

bool
predicate::evaluate (clause_t possible_truths) const
{
  int i;

  /* True remains true.  */
  if (*this == true)
    return true;

  gcc_assert (!(possible_truths & (1 << predicate::false_condition)));

  /* See if we can find clause we can disprove.  */
  for (i = 0; m_clause[i]; i++)
    {
      gcc_checking_assert (i < max_clauses);
      if (!(m_clause[i] & possible_truths))
	return false;
    }
  return true;
}

/* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
   instruction will be recomputed per invocation of the inlined call.  */

int
predicate::probability (conditions conds,
	                clause_t possible_truths,
	                vec<inline_param_summary> inline_param_summary) const
{
  int i;
  int combined_prob = REG_BR_PROB_BASE;

  /* True remains true.  */
  if (*this == true)
    return REG_BR_PROB_BASE;

  if (*this == false)
    return 0;

  gcc_assert (!(possible_truths & (1 << predicate::false_condition)));

  /* See if we can find clause we can disprove.  */
  for (i = 0; m_clause[i]; i++)
    {
      gcc_checking_assert (i < max_clauses);
      if (!(m_clause[i] & possible_truths))
	return 0;
      else
	{
	  int this_prob = 0;
	  int i2;
	  if (!inline_param_summary.exists ())
	    return REG_BR_PROB_BASE;
	  for (i2 = 0; i2 < num_conditions; i2++)
	    if ((m_clause[i] & possible_truths) & (1 << i2))
	      {
		if (i2 >= predicate::first_dynamic_condition)
		  {
		    condition *c =
		      &(*conds)[i2 - predicate::first_dynamic_condition];
		    if (c->code == predicate::changed
			&& (c->operand_num <
			    (int) inline_param_summary.length ()))
		      {
			int iprob =
			  inline_param_summary[c->operand_num].change_prob;
			this_prob = MAX (this_prob, iprob);
		      }
		    else
		      this_prob = REG_BR_PROB_BASE;
		  }
		else
		  this_prob = REG_BR_PROB_BASE;
	      }
	  combined_prob = MIN (this_prob, combined_prob);
	  if (!combined_prob)
	    return 0;
	}
    }
  return combined_prob;
}


/* Dump conditional COND.  */

void
dump_condition (FILE *f, conditions conditions, int cond)
{
  condition *c;
  if (cond == predicate::false_condition)
    fprintf (f, "false");
  else if (cond == predicate::not_inlined_condition)
    fprintf (f, "not inlined");
  else
    {
      c = &(*conditions)[cond - predicate::first_dynamic_condition];
      fprintf (f, "op%i", c->operand_num);
      if (c->agg_contents)
	fprintf (f, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
		 c->by_ref ? "ref " : "", c->offset);
      if (c->code == predicate::is_not_constant)
	{
	  fprintf (f, " not constant");
	  return;
	}
      if (c->code == predicate::changed)
	{
	  fprintf (f, " changed");
	  return;
	}
      fprintf (f, " %s ", op_symbol_code (c->code));
      print_generic_expr (f, c->val);
    }
}


/* Dump clause CLAUSE.  */

static void
dump_clause (FILE *f, conditions conds, clause_t clause)
{
  int i;
  bool found = false;
  fprintf (f, "(");
  if (!clause)
    fprintf (f, "true");
  for (i = 0; i < predicate::num_conditions; i++)
    if (clause & (1 << i))
      {
	if (found)
	  fprintf (f, " || ");
	found = true;
	dump_condition (f, conds, i);
      }
  fprintf (f, ")");
}


/* Dump THIS to F. CONDS a vector of conditions used when evauating
   predicats. When NL is true new line is output at the end of dump.  */

void
predicate::dump (FILE *f, conditions conds, bool nl) const
{
  int i;
  if (*this == true)
    dump_clause (f, conds, 0);
  else
    for (i = 0; m_clause[i]; i++)
      {
	if (i)
	  fprintf (f, " && ");
	dump_clause (f, conds, m_clause[i]);
      }
  if (nl)
    fprintf (f, "\n");
}


void
predicate::debug (conditions conds) const
{
  dump (stderr, conds);
}


/* Remap predicate THIS of former function to be predicate of duplicated function.
   POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
   INFO is inline summary of the duplicated node.  */

predicate
predicate::remap_after_duplication (clause_t possible_truths)
{
  int j;
  predicate out = true;
  for (j = 0; m_clause[j]; j++)
    if (!(possible_truths & m_clause[j]))
      return false;
    else
      out.add_clause (NULL, possible_truths & m_clause[j]);
  return out;
}


/* Translate all conditions from callee representation into caller
   representation and symbolically evaluate predicate THIS into new predicate.

   INFO is ipa_fn_summary of function we are adding predicate into, CALLEE_INFO
   is summary of function predicate P is from. OPERAND_MAP is array giving
   callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
   callee conditions that may be true in caller context.  TOPLEV_PREDICATE is
   predicate under which callee is executed.  OFFSET_MAP is an array of of
   offsets that need to be added to conditions, negative offset means that
   conditions relying on values passed by reference have to be discarded
   because they might not be preserved (and should be considered offset zero
   for other purposes).  */

predicate
predicate::remap_after_inlining (struct ipa_fn_summary *info,
				 struct ipa_fn_summary *callee_info,
				 vec<int> operand_map,
				 vec<int> offset_map,
				 clause_t possible_truths,
				 const predicate &toplev_predicate)
{
  int i;
  predicate out = true;

  /* True predicate is easy.  */
  if (*this == true)
    return toplev_predicate;
  for (i = 0; m_clause[i]; i++)
    {
      clause_t clause = m_clause[i];
      int cond;
      predicate clause_predicate = false;

      gcc_assert (i < max_clauses);

      for (cond = 0; cond < num_conditions; cond++)
	/* Do we have condition we can't disprove?   */
	if (clause & possible_truths & (1 << cond))
	  {
	    predicate cond_predicate;
	    /* Work out if the condition can translate to predicate in the
	       inlined function.  */
	    if (cond >= predicate::first_dynamic_condition)
	      {
		struct condition *c;

		c = &(*callee_info->conds)[cond
					   -
					   predicate::first_dynamic_condition];
		/* See if we can remap condition operand to caller's operand.
		   Otherwise give up.  */
		if (!operand_map.exists ()
		    || (int) operand_map.length () <= c->operand_num
		    || operand_map[c->operand_num] == -1
		    /* TODO: For non-aggregate conditions, adding an offset is
		       basically an arithmetic jump function processing which
		       we should support in future.  */
		    || ((!c->agg_contents || !c->by_ref)
			&& offset_map[c->operand_num] > 0)
		    || (c->agg_contents && c->by_ref
			&& offset_map[c->operand_num] < 0))
		  cond_predicate = true;
		else
		  {
		    struct agg_position_info ap;
		    HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
		    if (offset_delta < 0)
		      {
			gcc_checking_assert (!c->agg_contents || !c->by_ref);
			offset_delta = 0;
		      }
		    gcc_assert (!c->agg_contents
				|| c->by_ref || offset_delta == 0);
		    ap.offset = c->offset + offset_delta;
		    ap.agg_contents = c->agg_contents;
		    ap.by_ref = c->by_ref;
		    cond_predicate = add_condition (info,
						    operand_map[c->operand_num],
						    c->size, &ap, c->code,
						    c->val);
		  }
	      }
	    /* Fixed conditions remains same, construct single
	       condition predicate.  */
	    else
	      cond_predicate = predicate::predicate_testing_cond (cond);
	    clause_predicate = clause_predicate.or_with (info->conds,
					                 cond_predicate);
	  }
      out &= clause_predicate;
    }
  out &= toplev_predicate;
  return out;
}


/* Read predicate from IB.  */

void
predicate::stream_in (struct lto_input_block *ib)
{
  clause_t clause;
  int k = 0;

  do
    {
      gcc_assert (k <= max_clauses);
      clause = m_clause[k++] = streamer_read_uhwi (ib);
    }
  while (clause);

  /* Zero-initialize the remaining clauses in OUT.  */
  while (k <= max_clauses)
    m_clause[k++] = 0;
}


/* Write predicate P to OB.  */

void
predicate::stream_out (struct output_block *ob)
{
  int j;
  for (j = 0; m_clause[j]; j++)
    {
      gcc_assert (j < max_clauses);
      streamer_write_uhwi (ob, m_clause[j]);
    }
  streamer_write_uhwi (ob, 0);
}


/* Add condition to condition list SUMMARY. OPERAND_NUM, SIZE, CODE and VAL
   correspond to fields of condition structure.  AGGPOS describes whether the
   used operand is loaded from an aggregate and where in the aggregate it is.
   It can be NULL, which means this not a load from an aggregate.  */

predicate
add_condition (struct ipa_fn_summary *summary, int operand_num,
	       HOST_WIDE_INT size, struct agg_position_info *aggpos,
	       enum tree_code code, tree val)
{
  int i;
  struct condition *c;
  struct condition new_cond;
  HOST_WIDE_INT offset;
  bool agg_contents, by_ref;

  if (aggpos)
    {
      offset = aggpos->offset;
      agg_contents = aggpos->agg_contents;
      by_ref = aggpos->by_ref;
    }
  else
    {
      offset = 0;
      agg_contents = false;
      by_ref = false;
    }

  gcc_checking_assert (operand_num >= 0);
  for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
    {
      if (c->operand_num == operand_num
	  && c->size == size
	  && c->code == code
	  && c->val == val
	  && c->agg_contents == agg_contents
	  && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
	return predicate::predicate_testing_cond (i);
    }
  /* Too many conditions.  Give up and return constant true.  */
  if (i == predicate::num_conditions - predicate::first_dynamic_condition)
    return true;

  new_cond.operand_num = operand_num;
  new_cond.code = code;
  new_cond.val = val;
  new_cond.agg_contents = agg_contents;
  new_cond.by_ref = by_ref;
  new_cond.offset = offset;
  new_cond.size = size;
  vec_safe_push (summary->conds, new_cond);

  return predicate::predicate_testing_cond (i);
}