--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/ipa-predicate.c	Fri Oct 27 22:46:09 2017 +0900
@@ -0,0 +1,573 @@
+/* IPA predicates.
+   Copyright (C) 2003-2017 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);
+}