[thirdparty/gcc.git] / gcc / tree-ssa-ifcombine.c

/* Combining of if-expressions on trees.
   Copyright (C) 2007 Free Software Foundation, Inc.
   Contributed by Richard Guenther <rguenther@suse.de>

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 2, 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 COPYING.  If not, write to
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "basic-block.h"
#include "timevar.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-dump.h"

/* This pass combines COND_EXPRs to simplify control flow.  It
   currently recognizes bit tests and comparisons in chains that
   represent logical and or logical or of two COND_EXPRs.

   It does so by walking basic blocks in a approximate reverse
   post-dominator order and trying to match CFG patterns that
   represent logical and or logical or of two COND_EXPRs.
   Transformations are done if the COND_EXPR conditions match
   either

     1. two single bit tests X & (1 << Yn) (for logical and)

     2. two bit tests X & Yn (for logical or)

     3. two comparisons X OPn Y (for logical or)

   To simplify this pass, removing basic blocks and dead code
   is left to CFG cleanup and DCE.  */


/* Recognize a if-then-else CFG pattern starting to match with the
   COND_BB basic-block containing the COND_EXPR.  The recognized
   then end else blocks are stored to *THEN_BB and *ELSE_BB.  If
   *THEN_BB and/or *ELSE_BB are already set, they are required to
   match the then and else basic-blocks to make the pattern match.
   Returns true if the pattern matched, false otherwise.  */

static bool
recognize_if_then_else (basic_block cond_bb,
			basic_block *then_bb, basic_block *else_bb)
{
  edge t, e;

  if (EDGE_COUNT (cond_bb->succs) != 2)
    return false;

  /* Find the then/else edges.  */
  t = EDGE_SUCC (cond_bb, 0);
  e = EDGE_SUCC (cond_bb, 1);
  if (!(t->flags & EDGE_TRUE_VALUE))
    {
      edge tmp = t;
      t = e;
      e = tmp;
    }
  if (!(t->flags & EDGE_TRUE_VALUE)
      || !(e->flags & EDGE_FALSE_VALUE))
    return false;

  /* Check if the edge destinations point to the required block.  */
  if (*then_bb
      && t->dest != *then_bb)
    return false;
  if (*else_bb
      && e->dest != *else_bb)
    return false;

  if (!*then_bb)
    *then_bb = t->dest;
  if (!*else_bb)
    *else_bb = e->dest;

  return true;
}

/* Verify if the basic block BB does not have side-effects.  Return
   true in this case, else false.  */

static bool
bb_no_side_effects_p (basic_block bb)
{
  block_stmt_iterator bsi;

  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
    {
      tree stmt = bsi_stmt (bsi);
      stmt_ann_t ann = stmt_ann (stmt);

      if (ann->has_volatile_ops
	  || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
	return false;
    }

  return true;
}

/* Verify if all PHI node arguments in DEST for edges from BB1 or
   BB2 to DEST are the same.  This makes the CFG merge point
   free from side-effects.  Return true in this case, else false.  */

static bool
same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
{
  edge e1 = find_edge (bb1, dest);
  edge e2 = find_edge (bb2, dest);
  tree phi;

  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
    if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
			  PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
      return false;

  return true;
}

/* Recognize a single bit test pattern in COND_EXPR and its defining
   statements.  Store the name being tested in *NAME and the bit
   in *BIT.  The COND_EXPR computes *NAME & (1 << *BIT).
   Returns true if the pattern matched, false otherwise.  */

static bool
recognize_single_bit_test (tree cond_expr, tree *name, tree *bit)
{
  tree t;

  /* Get at the definition of the result of the bit test.  */
  t = TREE_OPERAND (cond_expr, 0);
  if (TREE_CODE (t) == NE_EXPR
      && integer_zerop (TREE_OPERAND (t, 1)))
    t = TREE_OPERAND (t, 0);
  if (TREE_CODE (t) != SSA_NAME)
    return false;
  t = SSA_NAME_DEF_STMT (t);
  if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
    return false;
  t = GIMPLE_STMT_OPERAND (t, 1);

  /* Look at which bit is tested.  One form to recognize is
     D.1985_5 = state_3(D) >> control1_4(D);
     D.1986_6 = (int) D.1985_5;
     D.1987_7 = op0 & 1;
     if (D.1987_7 != 0)  */
  if (TREE_CODE (t) == BIT_AND_EXPR
      && integer_onep (TREE_OPERAND (t, 1))
      && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
    {
      t = TREE_OPERAND (t, 0);
      do {
	t = SSA_NAME_DEF_STMT (t);
	if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
	  return false;
	t = GIMPLE_STMT_OPERAND (t, 1);
	if (TREE_CODE (t) == NOP_EXPR
	    || TREE_CODE (t) == CONVERT_EXPR)
	  t = TREE_OPERAND (t, 0);
      } while (TREE_CODE (t) == SSA_NAME);

      if (TREE_CODE (t) == RSHIFT_EXPR)
	{
	  /* op0 & (1 << op1) */
	  *bit = TREE_OPERAND (t, 1);
	  *name = TREE_OPERAND (t, 0);
	}
      else
	{
	  /* t & 1 */
	  *bit = integer_one_node;
	  *name = t;
	}

      return true;
    }

  /* Another form is
     D.1987_7 = op0 & (1 << CST)
     if (D.1987_7 != 0)  */
  if (TREE_CODE (t) == BIT_AND_EXPR
      && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
      && integer_pow2p (TREE_OPERAND (t, 1)))
    {
      *name = TREE_OPERAND (t, 0);
      *bit = build_int_cst (integer_type_node,
			    tree_log2 (TREE_OPERAND (t, 1)));
      return true;
    }

  /* Another form is
     D.1986_6 = 1 << control1_4(D)
     D.1987_7 = op0 & D.1986_6
     if (D.1987_7 != 0)  */
  if (TREE_CODE (t) == BIT_AND_EXPR
      && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
      && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
    {
      tree tmp;

      /* Both arguments of the BIT_AND_EXPR can be the single-bit
	 specifying expression.  */
      tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
      if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
	  && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
	  && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
	{
	  *name = TREE_OPERAND (t, 1);
	  *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
	  return true;
	}

      tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
      if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
	  && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
	  && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
	{
	  *name = TREE_OPERAND (t, 0);
	  *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
	  return true;
	}
    }

  return false;
}

/* Recognize a bit test pattern in COND_EXPR and its defining
   statements.  Store the name being tested in *NAME and the bits
   in *BITS.  The COND_EXPR computes *NAME & *BITS.
   Returns true if the pattern matched, false otherwise.  */

static bool
recognize_bits_test (tree cond_expr, tree *name, tree *bits)
{
  tree t;

  /* Get at the definition of the result of the bit test.  */
  t = TREE_OPERAND (cond_expr, 0);
  if (TREE_CODE (t) == NE_EXPR
      && integer_zerop (TREE_OPERAND (t, 1)))
    t = TREE_OPERAND (t, 0);
  if (TREE_CODE (t) != SSA_NAME)
    return false;
  t = SSA_NAME_DEF_STMT (t);
  if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
    return false;
  t = GIMPLE_STMT_OPERAND (t, 1);

  if (TREE_CODE (t) != BIT_AND_EXPR)
    return false;

  *name = TREE_OPERAND (t, 0);
  *bits = TREE_OPERAND (t, 1);

  return true;
}

/* If-convert on a and pattern with a common else block.  The inner
   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
   Returns true if the edges to the common else basic-block were merged.  */

static bool
ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
{
  block_stmt_iterator bsi;
  tree inner_cond, outer_cond;
  tree name1, name2, bit1, bit2;

  inner_cond = last_stmt (inner_cond_bb);
  if (!inner_cond
      || TREE_CODE (inner_cond) != COND_EXPR)
    return false;

  outer_cond = last_stmt (outer_cond_bb);
  if (!outer_cond
      || TREE_CODE (outer_cond) != COND_EXPR)
    return false;

  /* See if we test a single bit of the same name in both tests.  In
     that case remove the outer test, merging both else edges,
     and change the inner one to test for
     name & (bit1 | bit2) == (bit1 | bit2).  */
  if (recognize_single_bit_test (inner_cond, &name1, &bit1)
      && recognize_single_bit_test (outer_cond, &name2, &bit2)
      && name1 == name2)
    {
      tree t, t2;

      /* Do it.  */
      bsi = bsi_for_stmt (inner_cond);
      t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
		       integer_one_node, bit1);
      t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
		        integer_one_node, bit2);
      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
      t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
      t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
      t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE);
      COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
						 t2, t);
      update_stmt (inner_cond);

      /* Leave CFG optimization to cfg_cleanup.  */
      COND_EXPR_COND (outer_cond) = boolean_true_node;
      update_stmt (outer_cond);

      if (dump_file)
	{
	  fprintf (dump_file, "optimizing double bit test to ");
	  print_generic_expr (dump_file, name1, 0);
	  fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
	  print_generic_expr (dump_file, bit1, 0);
	  fprintf (dump_file, ") | (1 << ");
	  print_generic_expr (dump_file, bit2, 0);
	  fprintf (dump_file, ")\n");
	}

      return true;
    }

  return false;
}

/* If-convert on a or pattern with a common then block.  The inner
   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
   Returns true, if the edges leading to the common then basic-block
   were merged.  */

static bool
ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
{
  tree inner_cond, outer_cond;
  tree name1, name2, bits1, bits2;

  inner_cond = last_stmt (inner_cond_bb);
  if (!inner_cond
      || TREE_CODE (inner_cond) != COND_EXPR)
    return false;

  outer_cond = last_stmt (outer_cond_bb);
  if (!outer_cond
      || TREE_CODE (outer_cond) != COND_EXPR)
    return false;

  /* See if we have two bit tests of the same name in both tests.
     In that case remove the outer test and change the inner one to
     test for name & (bits1 | bits2) != 0.  */
  if (recognize_bits_test (inner_cond, &name1, &bits1)
      && recognize_bits_test (outer_cond, &name2, &bits2))
    {
      block_stmt_iterator bsi;
      tree t;

      /* Find the common name which is bit-tested.  */
      if (name1 == name2)
	;
      else if (bits1 == bits2)
	{
	  t = name2;
	  name2 = bits2;
	  bits2 = t;
	  t = name1;
	  name1 = bits1;
	  bits1 = t;
	}
      else if (name1 == bits2)
	{
	  t = name2;
	  name2 = bits2;
	  bits2 = t;
	}
      else if (bits1 == name2)
	{
	  t = name1;
	  name1 = bits1;
	  bits1 = t;
	}
      else
	return false;

      /* Do it.  */
      bsi = bsi_for_stmt (inner_cond);
      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
      t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
      t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
      t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
      COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
						 build_int_cst (TREE_TYPE (t), 0));
      update_stmt (inner_cond);

      /* Leave CFG optimization to cfg_cleanup.  */
      COND_EXPR_COND (outer_cond) = boolean_false_node;
      update_stmt (outer_cond);

      if (dump_file)
	{
	  fprintf (dump_file, "optimizing bits or bits test to ");
	  print_generic_expr (dump_file, name1, 0);
	  fprintf (dump_file, " & T != 0\nwith temporary T = ");
	  print_generic_expr (dump_file, bits1, 0);
	  fprintf (dump_file, " | ");
	  print_generic_expr (dump_file, bits2, 0);
	  fprintf (dump_file, "\n");
	}

      return true;
    }

  /* See if we have two comparisons that we can merge into one.
     This happens for C++ operator overloading where for example
     GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
  else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
	   && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
	   && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
			       TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
	   && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
			       TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
    {
      tree ccond1 = COND_EXPR_COND (inner_cond);
      tree ccond2 = COND_EXPR_COND (outer_cond);
      enum tree_code code1 = TREE_CODE (ccond1);
      enum tree_code code2 = TREE_CODE (ccond2);
      enum tree_code code;
      tree t;

#define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
		  || (code2 == a ## _EXPR && code1 == b ## _EXPR))
      /* Merge the two condition codes if possible.  */
      if (code1 == code2)
	code = code1;
      else if (CHK (EQ, LT))
	code = LE_EXPR;
      else if (CHK (EQ, GT))
	code = GE_EXPR;
      else if (CHK (LT, LE))
	code = LE_EXPR;
      else if (CHK (GT, GE))
	code = GE_EXPR;
      else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
	       || flag_unsafe_math_optimizations)
	{
	  if (CHK (LT, GT))
	    code = NE_EXPR;
	  else if (CHK (LT, NE))
	    code = NE_EXPR;
	  else if (CHK (GT, NE))
	    code = NE_EXPR;
	  else
	    return false;
	}
      /* We could check for combinations leading to trivial true/false.  */
      else
	return false;
#undef CHK

      /* Do it.  */
      t = fold_build2 (code, boolean_type_node,
		       TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
      COND_EXPR_COND (inner_cond) = t;
      update_stmt (inner_cond);

      /* Leave CFG optimization to cfg_cleanup.  */
      COND_EXPR_COND (outer_cond) = boolean_false_node;
      update_stmt (outer_cond);

      if (dump_file)
	{
	  fprintf (dump_file, "optimizing two comparisons to ");
	  print_generic_expr (dump_file, t, 0);
	  fprintf (dump_file, "\n");
	}

      return true;
    }

  return false;
}

/* Recognize a CFG pattern and dispatch to the appropriate
   if-conversion helper.  We start with BB as the innermost
   worker basic-block.  Returns true if a transformation was done.  */

static bool
tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
{
  basic_block then_bb = NULL, else_bb = NULL;

  if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
    return false;

  /* Recognize && and || of two conditions with a common
     then/else block which entry edges we can merge.  That is:
       if (a || b)
	 ;
     and
       if (a && b)
	 ;
     This requires a single predecessor of the inner cond_bb.  */
  if (single_pred_p (inner_cond_bb))
    {
      basic_block outer_cond_bb = single_pred (inner_cond_bb);

      /* The && form is characterized by a common else_bb with
	 the two edges leading to it mergable.  The latter is
	 guaranteed by matching PHI arguments in the else_bb and
	 the inner cond_bb having no side-effects.  */
      if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
	  && bb_no_side_effects_p (inner_cond_bb))
	{
	  /* We have
	       <outer_cond_bb>
		 if (q) goto inner_cond_bb; else goto else_bb;
	       <inner_cond_bb>
		 if (p) goto ...; else goto else_bb;
		 ...
	       <else_bb>
		 ...
	   */
	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
	}

      /* The || form is characterized by a common then_bb with the
	 two edges leading to it mergable.  The latter is guaranteed
         by matching PHI arguments in the then_bb and the inner cond_bb
	 having no side-effects.  */
      if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
	  && bb_no_side_effects_p (inner_cond_bb))
	{
	  /* We have
	       <outer_cond_bb>
		 if (q) goto then_bb; else goto inner_cond_bb;
	       <inner_cond_bb>
		 if (q) goto then_bb; else goto ...;
	       <then_bb>
		 ...
	   */
	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
	}
    }

  return false;
}

/* Main entry for the tree if-conversion pass.  */

static unsigned int
tree_ssa_ifcombine (void)
{
  basic_block *bbs;
  bool cfg_changed = false;
  int i;

  bbs = blocks_in_phiopt_order ();

  for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
    {
      basic_block bb = bbs[i];
      tree stmt = last_stmt (bb);

      if (stmt
	  && TREE_CODE (stmt) == COND_EXPR)
	cfg_changed |= tree_ssa_ifcombine_bb (bb);
    }

  free (bbs);

  return cfg_changed ? TODO_cleanup_cfg : 0;
}

static bool
gate_ifcombine (void)
{
  return 1;
}

struct tree_opt_pass pass_tree_ifcombine = {
  "ifcombine",			/* name */
  gate_ifcombine,		/* gate */
  tree_ssa_ifcombine,		/* execute */
  NULL,				/* sub */
  NULL,				/* next */
  0,				/* static_pass_number */
  TV_TREE_IFCOMBINE,		/* tv_id */
  PROP_cfg | PROP_ssa,		/* properties_required */
  0,				/* properties_provided */
  0,				/* properties_destroyed */
  0,				/* todo_flags_start */
  TODO_dump_func
  | TODO_ggc_collect
  | TODO_update_ssa
  | TODO_verify_ssa,		/* todo_flags_finish */
  0				/* letter */
};
Commit	Line	Data
8530c7be	1	/* Combining of if-expressions on trees.
	2	Copyright (C) 2007 Free Software Foundation, Inc.
	3	Contributed by Richard Guenther <rguenther@suse.de>
	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 2, or (at your option)
	10	any later version.
	11
	12	GCC is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING. If not, write to
	19	the Free Software Foundation, 51 Franklin Street, Fifth Floor,
	20	Boston, MA 02110-1301, USA. */
	21
	22	#include "config.h"
	23	#include "system.h"
	24	#include "coretypes.h"
	25	#include "tm.h"
	26	#include "tree.h"
	27	#include "basic-block.h"
	28	#include "timevar.h"
	29	#include "diagnostic.h"
	30	#include "tree-flow.h"
	31	#include "tree-pass.h"
	32	#include "tree-dump.h"
	33
	34	/* This pass combines COND_EXPRs to simplify control flow. It
	35	currently recognizes bit tests and comparisons in chains that
	36	represent logical and or logical or of two COND_EXPRs.
	37
	38	It does so by walking basic blocks in a approximate reverse
	39	post-dominator order and trying to match CFG patterns that
	40	represent logical and or logical or of two COND_EXPRs.
	41	Transformations are done if the COND_EXPR conditions match
	42	either
	43
	44	1. two single bit tests X & (1 << Yn) (for logical and)
	45
	46	2. two bit tests X & Yn (for logical or)
	47
	48	3. two comparisons X OPn Y (for logical or)
	49
	50	To simplify this pass, removing basic blocks and dead code
	51	is left to CFG cleanup and DCE. */
	52
	53
	54	/* Recognize a if-then-else CFG pattern starting to match with the
	55	COND_BB basic-block containing the COND_EXPR. The recognized
	56	then end else blocks are stored to THEN_BB and ELSE_BB. If
	57	THEN_BB and/or ELSE_BB are already set, they are required to
	58	match the then and else basic-blocks to make the pattern match.
	59	Returns true if the pattern matched, false otherwise. */
	60
	61	static bool
	62	recognize_if_then_else (basic_block cond_bb,
	63	basic_block then_bb, basic_block else_bb)
	64	{
65	edge t, e;
66
67	if (EDGE_COUNT (cond_bb->succs) != 2)
68	return false;
69
70	/* Find the then/else edges. */
71	t = EDGE_SUCC (cond_bb, 0);
72	e = EDGE_SUCC (cond_bb, 1);
73	if (!(t->flags & EDGE_TRUE_VALUE))
74	{
75	edge tmp = t;
76	t = e;
77	e = tmp;
78	}
79	if (!(t->flags & EDGE_TRUE_VALUE)
80	\|\| !(e->flags & EDGE_FALSE_VALUE))
81	return false;
82
83	/* Check if the edge destinations point to the required block. */
84	if (*then_bb
85	&& t->dest != *then_bb)
86	return false;
87	if (*else_bb
88	&& e->dest != *else_bb)
89	return false;
90
91	if (!*then_bb)
92	*then_bb = t->dest;
93	if (!*else_bb)
94	*else_bb = e->dest;
95
96	return true;
97	}
98
99	/* Verify if the basic block BB does not have side-effects. Return
100	true in this case, else false. */
101
102	static bool
103	bb_no_side_effects_p (basic_block bb)
104	{
105	block_stmt_iterator bsi;
106
107	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
108	{
109	tree stmt = bsi_stmt (bsi);
110	stmt_ann_t ann = stmt_ann (stmt);
111
112	if (ann->has_volatile_ops
113	\|\| !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
114	return false;
115	}
116
117	return true;
118	}
119
120	/* Verify if all PHI node arguments in DEST for edges from BB1 or
121	BB2 to DEST are the same. This makes the CFG merge point
122	free from side-effects. Return true in this case, else false. */
123
124	static bool
125	same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
126	{
127	edge e1 = find_edge (bb1, dest);
128	edge e2 = find_edge (bb2, dest);
129	tree phi;
130
131	for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
132	if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
133	PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
134	return false;
135
136	return true;
137	}
138
139	/* Recognize a single bit test pattern in COND_EXPR and its defining
140	statements. Store the name being tested in *NAME and the bit
141	in BIT. The COND_EXPR computes NAME & (1 << *BIT).
142	Returns true if the pattern matched, false otherwise. */
143
144	static bool
145	recognize_single_bit_test (tree cond_expr, tree name, tree bit)
146	{
147	tree t;
148
149	/* Get at the definition of the result of the bit test. */
150	t = TREE_OPERAND (cond_expr, 0);
151	if (TREE_CODE (t) == NE_EXPR
152	&& integer_zerop (TREE_OPERAND (t, 1)))
153	t = TREE_OPERAND (t, 0);
154	if (TREE_CODE (t) != SSA_NAME)
155	return false;
156	t = SSA_NAME_DEF_STMT (t);
157	if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
158	return false;
159	t = GIMPLE_STMT_OPERAND (t, 1);
160
161	/* Look at which bit is tested. One form to recognize is
162	D.1985_5 = state_3(D) >> control1_4(D);
163	D.1986_6 = (int) D.1985_5;
164	D.1987_7 = op0 & 1;
165	if (D.1987_7 != 0) */
166	if (TREE_CODE (t) == BIT_AND_EXPR
167	&& integer_onep (TREE_OPERAND (t, 1))
168	&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
169	{
170	t = TREE_OPERAND (t, 0);
171	do {
172	t = SSA_NAME_DEF_STMT (t);
173	if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
174	return false;
175	t = GIMPLE_STMT_OPERAND (t, 1);
176	if (TREE_CODE (t) == NOP_EXPR
177	\|\| TREE_CODE (t) == CONVERT_EXPR)
178	t = TREE_OPERAND (t, 0);
179	} while (TREE_CODE (t) == SSA_NAME);
180
181	if (TREE_CODE (t) == RSHIFT_EXPR)
182	{
183	/* op0 & (1 << op1) */
184	*bit = TREE_OPERAND (t, 1);
185	*name = TREE_OPERAND (t, 0);
186	}
187	else
188	{
189	/* t & 1 */
190	*bit = integer_one_node;
191	*name = t;
192	}
193
194	return true;
195	}
196
197	/* Another form is
198	D.1987_7 = op0 & (1 << CST)
199	if (D.1987_7 != 0) */
200	if (TREE_CODE (t) == BIT_AND_EXPR
201	&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
202	&& integer_pow2p (TREE_OPERAND (t, 1)))
203	{
204	*name = TREE_OPERAND (t, 0);
205	*bit = build_int_cst (integer_type_node,
206	tree_log2 (TREE_OPERAND (t, 1)));
207	return true;
208	}
209
210	/* Another form is
211	D.1986_6 = 1 << control1_4(D)
212	D.1987_7 = op0 & D.1986_6
213	if (D.1987_7 != 0) */
214	if (TREE_CODE (t) == BIT_AND_EXPR
215	&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
216	&& TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
217	{
218	tree tmp;
219
220	/* Both arguments of the BIT_AND_EXPR can be the single-bit
221	specifying expression. */
222	tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
223	if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
224	&& TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
225	&& integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
226	{
227	*name = TREE_OPERAND (t, 1);
228	*bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
229	return true;
230	}
231
232	tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
233	if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
234	&& TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
235	&& integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
236	{
237	*name = TREE_OPERAND (t, 0);
238	*bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
239	return true;
240	}
241	}
242
243	return false;
244	}
245
246	/* Recognize a bit test pattern in COND_EXPR and its defining
247	statements. Store the name being tested in *NAME and the bits
248	in BITS. The COND_EXPR computes NAME & *BITS.
249	Returns true if the pattern matched, false otherwise. */
250
251	static bool
252	recognize_bits_test (tree cond_expr, tree name, tree bits)
253	{
254	tree t;
255
256	/* Get at the definition of the result of the bit test. */
257	t = TREE_OPERAND (cond_expr, 0);
258	if (TREE_CODE (t) == NE_EXPR
259	&& integer_zerop (TREE_OPERAND (t, 1)))
260	t = TREE_OPERAND (t, 0);
261	if (TREE_CODE (t) != SSA_NAME)
262	return false;
263	t = SSA_NAME_DEF_STMT (t);
264	if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
265	return false;
266	t = GIMPLE_STMT_OPERAND (t, 1);
267
268	if (TREE_CODE (t) != BIT_AND_EXPR)
269	return false;
270
271	*name = TREE_OPERAND (t, 0);
272	*bits = TREE_OPERAND (t, 1);
273
274	return true;
275	}
276
277	/* If-convert on a and pattern with a common else block. The inner
278	if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
279	Returns true if the edges to the common else basic-block were merged. */
280
281	static bool
282	ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
283	{
284	block_stmt_iterator bsi;
285	tree inner_cond, outer_cond;
286	tree name1, name2, bit1, bit2;
287
288	inner_cond = last_stmt (inner_cond_bb);
289	if (!inner_cond
290	\|\| TREE_CODE (inner_cond) != COND_EXPR)
291	return false;
292
293	outer_cond = last_stmt (outer_cond_bb);
294	if (!outer_cond
295	\|\| TREE_CODE (outer_cond) != COND_EXPR)
296	return false;
297
298	/* See if we test a single bit of the same name in both tests. In
299	that case remove the outer test, merging both else edges,
300	and change the inner one to test for
301	name & (bit1 \| bit2) == (bit1 \| bit2). */
302	if (recognize_single_bit_test (inner_cond, &name1, &bit1)
303	&& recognize_single_bit_test (outer_cond, &name2, &bit2)
304	&& name1 == name2)
305	{
306	tree t, t2;
307
308	/* Do it. */
309	bsi = bsi_for_stmt (inner_cond);
310	t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
311	integer_one_node, bit1);
312	t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
313	integer_one_node, bit2);
314	t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
315	t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
316	t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
317	t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE);
318	COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
319	t2, t);
320	update_stmt (inner_cond);
321
322	/* Leave CFG optimization to cfg_cleanup. */
323	COND_EXPR_COND (outer_cond) = boolean_true_node;
324	update_stmt (outer_cond);
325
326	if (dump_file)
327	{
328	fprintf (dump_file, "optimizing double bit test to ");
329	print_generic_expr (dump_file, name1, 0);
330	fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
331	print_generic_expr (dump_file, bit1, 0);
332	fprintf (dump_file, ") \| (1 << ");
333	print_generic_expr (dump_file, bit2, 0);
334	fprintf (dump_file, ")\n");
335	}
336
337	return true;
338	}
339
340	return false;
341	}
342
343	/* If-convert on a or pattern with a common then block. The inner
344	if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
345	Returns true, if the edges leading to the common then basic-block
346	were merged. */
347
348	static bool
349	ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
350	{
351	tree inner_cond, outer_cond;
352	tree name1, name2, bits1, bits2;
353
354	inner_cond = last_stmt (inner_cond_bb);
355	if (!inner_cond
356	\|\| TREE_CODE (inner_cond) != COND_EXPR)
357	return false;
358
359	outer_cond = last_stmt (outer_cond_bb);
360	if (!outer_cond
361	\|\| TREE_CODE (outer_cond) != COND_EXPR)
362	return false;
363
364	/* See if we have two bit tests of the same name in both tests.
365	In that case remove the outer test and change the inner one to
366	test for name & (bits1 \| bits2) != 0. */
367	if (recognize_bits_test (inner_cond, &name1, &bits1)
368	&& recognize_bits_test (outer_cond, &name2, &bits2))
369	{
370	block_stmt_iterator bsi;
371	tree t;
372
373	/* Find the common name which is bit-tested. */
374	if (name1 == name2)
375	;
376	else if (bits1 == bits2)
377	{
378	t = name2;
379	name2 = bits2;
380	bits2 = t;
381	t = name1;
382	name1 = bits1;
383	bits1 = t;
384	}
385	else if (name1 == bits2)
386	{
387	t = name2;
388	name2 = bits2;
389	bits2 = t;
390	}
391	else if (bits1 == name2)
392	{
393	t = name1;
394	name1 = bits1;
395	bits1 = t;
396	}
397	else
398	return false;
399
400	/* Do it. */
401	bsi = bsi_for_stmt (inner_cond);
402	t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
403	t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
404	t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
405	t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
406	COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
407	build_int_cst (TREE_TYPE (t), 0));
408	update_stmt (inner_cond);
409
410	/* Leave CFG optimization to cfg_cleanup. */
411	COND_EXPR_COND (outer_cond) = boolean_false_node;
412	update_stmt (outer_cond);
413
414	if (dump_file)
415	{
416	fprintf (dump_file, "optimizing bits or bits test to ");
417	print_generic_expr (dump_file, name1, 0);
418	fprintf (dump_file, " & T != 0\nwith temporary T = ");
419	print_generic_expr (dump_file, bits1, 0);
420	fprintf (dump_file, " \| ");
421	print_generic_expr (dump_file, bits2, 0);
422	fprintf (dump_file, "\n");
423	}
424
425	return true;
426	}
427
428	/* See if we have two comparisons that we can merge into one.
429	This happens for C++ operator overloading where for example
430	GE_EXPR is implemented as GT_EXPR \|\| EQ_EXPR. */
431	else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
432	&& COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
433	&& operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
434	TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
435	&& operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
436	TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
437	{
438	tree ccond1 = COND_EXPR_COND (inner_cond);
439	tree ccond2 = COND_EXPR_COND (outer_cond);
440	enum tree_code code1 = TREE_CODE (ccond1);
441	enum tree_code code2 = TREE_CODE (ccond2);
442	enum tree_code code;
443	tree t;
444
445	#define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
446	\|\| (code2 == a ## _EXPR && code1 == b ## _EXPR))
447	/* Merge the two condition codes if possible. */
448	if (code1 == code2)
449	code = code1;
450	else if (CHK (EQ, LT))
451	code = LE_EXPR;
452	else if (CHK (EQ, GT))
453	code = GE_EXPR;
454	else if (CHK (LT, LE))
455	code = LE_EXPR;
456	else if (CHK (GT, GE))
457	code = GE_EXPR;
458	else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
459	\|\| flag_unsafe_math_optimizations)
460	{
461	if (CHK (LT, GT))
462	code = NE_EXPR;
463	else if (CHK (LT, NE))
464	code = NE_EXPR;
465	else if (CHK (GT, NE))
466	code = NE_EXPR;
467	else
468	return false;
469	}
470	/* We could check for combinations leading to trivial true/false. */
471	else
472	return false;
473	#undef CHK
474
475	/* Do it. */
476	t = fold_build2 (code, boolean_type_node,
477	TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
478	COND_EXPR_COND (inner_cond) = t;
479	update_stmt (inner_cond);
480
481	/* Leave CFG optimization to cfg_cleanup. */
482	COND_EXPR_COND (outer_cond) = boolean_false_node;
483	update_stmt (outer_cond);
484
485	if (dump_file)
486	{
487	fprintf (dump_file, "optimizing two comparisons to ");
488	print_generic_expr (dump_file, t, 0);
489	fprintf (dump_file, "\n");
490	}
491
492	return true;
493	}
494
495	return false;
496	}
497
498	/* Recognize a CFG pattern and dispatch to the appropriate
499	if-conversion helper. We start with BB as the innermost
500	worker basic-block. Returns true if a transformation was done. */
501
502	static bool
503	tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
504	{
505	basic_block then_bb = NULL, else_bb = NULL;
506
507	if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
508	return false;
509
510	/* Recognize && and \|\| of two conditions with a common
511	then/else block which entry edges we can merge. That is:
512	if (a \|\| b)
513	;
514	and
515	if (a && b)
516	;
517	This requires a single predecessor of the inner cond_bb. */
518	if (single_pred_p (inner_cond_bb))
519	{
520	basic_block outer_cond_bb = single_pred (inner_cond_bb);
521
522	/* The && form is characterized by a common else_bb with
523	the two edges leading to it mergable. The latter is
524	guaranteed by matching PHI arguments in the else_bb and
525	the inner cond_bb having no side-effects. */
526	if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
527	&& same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
528	&& bb_no_side_effects_p (inner_cond_bb))
529	{
530	/* We have
531	<outer_cond_bb>
532	if (q) goto inner_cond_bb; else goto else_bb;
533	<inner_cond_bb>
534	if (p) goto ...; else goto else_bb;
535	...
536	<else_bb>
537	...
538	*/
539	return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
540	}
541
542	/* The \|\| form is characterized by a common then_bb with the
543	two edges leading to it mergable. The latter is guaranteed
544	by matching PHI arguments in the then_bb and the inner cond_bb
545	having no side-effects. */
546	if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
547	&& same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
548	&& bb_no_side_effects_p (inner_cond_bb))
549	{
550	/* We have
551	<outer_cond_bb>
552	if (q) goto then_bb; else goto inner_cond_bb;
553	<inner_cond_bb>
554	if (q) goto then_bb; else goto ...;
555	<then_bb>
556	...
557	*/
558	return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
559	}
560	}
561
562	return false;
563	}
564
565	/* Main entry for the tree if-conversion pass. */
566
567	static unsigned int
568	tree_ssa_ifcombine (void)
569	{
570	basic_block *bbs;
571	bool cfg_changed = false;
572	int i;
573
574	bbs = blocks_in_phiopt_order ();
575
576	for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
577	{
578	basic_block bb = bbs[i];
579	tree stmt = last_stmt (bb);
580
581	if (stmt
582	&& TREE_CODE (stmt) == COND_EXPR)
583	cfg_changed \|= tree_ssa_ifcombine_bb (bb);
584	}
585
586	free (bbs);
587
588	return cfg_changed ? TODO_cleanup_cfg : 0;
589	}
590
591	static bool
592	gate_ifcombine (void)
593	{
594	return 1;
595	}
596
597	struct tree_opt_pass pass_tree_ifcombine = {
598	"ifcombine", /* name */
599	gate_ifcombine, /* gate */
600	tree_ssa_ifcombine, /* execute */
601	NULL, /* sub */
602	NULL, /* next */
603	0, /* static_pass_number */
604	TV_TREE_IFCOMBINE, /* tv_id */
605	PROP_cfg \| PROP_ssa, /* properties_required */
606	0, /* properties_provided */
607	0, /* properties_destroyed */
608	0, /* todo_flags_start */
609	TODO_dump_func
610	\| TODO_ggc_collect
611	\| TODO_update_ssa
612	\| TODO_verify_ssa, /* todo_flags_finish */
613	0 /* letter */
614	};