Merge tree-ssa-20020619-branch into mainline.

From-SVN: r81764

1 files changed, 306 insertions, 0 deletions

diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
new file mode 100644
index 0000000..ea7a946
--- /dev/null
+++ b/gcc/tree-ssa-phiopt.c
@@ -0,0 +1,306 @@
+/* Optimization of PHI nodes by converting them into straightline code.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+
+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, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "basic-block.h"
+#include "timevar.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "tree-dump.h"
+#include "langhooks.h"
+
+static void tree_ssa_phiopt (void);
+static bool conditional_replacement (basic_block bb, tree phi, tree arg0,
+                                     tree arg1);
+
+
+/* This pass eliminates PHI nodes which can be trivially implemented as
+   an assignment from a conditional expression.  ie if we have something
+   like:
+
+     bb0:
+      if (cond) goto bb2; else goto bb1;
+     bb1:
+     bb2:
+      x = PHI (0 (bb1), 1 (bb0)
+
+    We can rewrite that as:
+    
+    bb0:
+    bb1:
+    bb2:
+      x = cond;
+
+    bb1 will become unreachable and bb0 and bb2 will almost always
+    be merged into a single block.  This occurs often due to gimplification
+    of conditionals.  */
+   
+static void
+tree_ssa_phiopt (void)
+{
+  basic_block bb;
+  bool removed_phis = false;
+
+  /* Search every basic block for PHI nodes we may be able to optimize.  */
+  FOR_EACH_BB (bb)
+    {
+      tree arg0, arg1, phi;
+
+
+      /* We're searching for blocks with one PHI node which has two
+	 arguments.  */
+      phi = phi_nodes (bb);
+      if (phi && TREE_CHAIN (phi) == NULL
+	  && PHI_NUM_ARGS (phi) == 2)
+        {
+
+            arg0 = PHI_ARG_DEF (phi, 0);
+            arg1 = PHI_ARG_DEF (phi, 1);
+            
+            /* Do the replacement of conditional if it can be done.  */
+            if (conditional_replacement (bb, phi, arg0, arg1))
+              {
+                /* We have done the replacement so we need to rebuild the cfg.   */
+                removed_phis = true;
+                continue;
+              }
+        }
+    }
+
+  /* If we removed any PHIs, then we have unreachable blocks and blocks
+     which need to be merged in the CFG.  */
+  if (removed_phis)
+    cleanup_tree_cfg ();
+}
+
+/*  The function conditional_replacement does the main work of doing the conditional
+    replacement.  Return true if the replacement is done.  Otherwise return false.
+    bb is the basic block where the replacement is going to be done on.  arg0
+    is argument 0 from the phi.  Likewise for arg1.   */
+
+static bool
+conditional_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
+{
+  tree result;
+  basic_block other_block = NULL;
+  basic_block cond_block = NULL;
+  tree last0, last1, new, cond;
+  block_stmt_iterator bsi;
+  edge true_edge, false_edge;
+
+  /* The PHI arguments have the constants 0 and 1, then convert
+    it to the conditional.  */
+  if ((integer_zerop (arg0) && integer_onep (arg1))
+      || (integer_zerop (arg1) && integer_onep (arg0)))
+    ;
+  else
+    return false;
+  
+  /* One of the alternatives must come from a block ending with
+      a COND_EXPR.  The other block must be entirely empty, except
+      for labels.  */
+  last0 = last_stmt (bb->pred->src);
+  last1 = last_stmt (bb->pred->pred_next->src);
+  if (last0 && TREE_CODE (last0) == COND_EXPR)
+    {
+      cond_block = bb->pred->src;
+      other_block = bb->pred->pred_next->src;
+    }
+  else if (last1 && TREE_CODE (last1) == COND_EXPR)
+    {
+      other_block = bb->pred->src;
+      cond_block = bb->pred->pred_next->src;
+    }
+  else
+    return false;
+  
+  /* COND_BLOCK must have precisely two successors.  We indirectly
+      verify that those successors are BB and OTHER_BLOCK.  */
+  if (!cond_block->succ
+      || !cond_block->succ->succ_next
+      || cond_block->succ->succ_next->succ_next
+      || (cond_block->succ->flags & EDGE_ABNORMAL) != 0
+      || (cond_block->succ->succ_next->flags & EDGE_ABNORMAL) != 0)
+    return false;
+  
+  /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK,
+      OTHER_BLOCK must have a single successor which is BB and
+      OTHER_BLOCK must have no PHI nodes.  */
+  if (!other_block->pred
+      || other_block->pred->src != cond_block
+      || other_block->pred->pred_next
+      || !other_block->succ
+      || other_block->succ->dest != bb
+      || other_block->succ->succ_next
+      || phi_nodes (other_block))
+    return false;
+  
+  /* OTHER_BLOCK must have no executable statements.  */
+  bsi = bsi_start (other_block);
+  while (!bsi_end_p (bsi)
+          && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
+              || IS_EMPTY_STMT (bsi_stmt (bsi))))
+    bsi_next (&bsi);
+  
+  if (!bsi_end_p (bsi))
+    return false;
+  
+  /* If the condition is not a naked SSA_NAME and its type does not
+      match the type of the result, then we can not optimize this case
+      as it would likely create non-gimple code when the condition
+      was converted to the result's type.  */
+  cond = COND_EXPR_COND (last_stmt (cond_block));
+  result = PHI_RESULT (phi);
+  if (TREE_CODE (cond) != SSA_NAME
+      && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
+    return false;
+  
+  /* If the condition was a naked SSA_NAME and the type is not the
+      same as the type of the result, then convert the type of the
+      condition.  */
+  if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
+    cond = fold_convert (TREE_TYPE (result), cond);
+  
+  /* We need to know which is the true edge and which is the false
+      edge so that we know when to invert the condition below.  */
+  extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
+  
+  /* At this point we know we have a COND_EXPR with two successors.
+      One successor is BB, the other successor is an empty block which
+      falls through into BB.
+  
+      There is a single PHI node at the join point (BB) and its arguments
+      are constants (0, 1).
+  
+      So, given the condition COND, and the two PHI arguments, we can
+      rewrite this PHI into non-branching code: 
+  
+        dest = (COND) or dest = COND'
+  
+      We use the condition as-is if the argument associated with the
+      true edge has the value one or the argument associated with the
+      false edge as the value zero.  Note that those conditions are not
+      the same since only one of the outgoing edges from the COND_EXPR
+      will directly reach BB and thus be associated with an argument.  */
+  if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0))
+      || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0))
+      || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1))
+      || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1)))
+    {
+      new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+                    PHI_RESULT (phi), cond);
+    }
+  else
+    {
+      cond = invert_truthvalue (cond);
+  
+      if (is_gimple_cast (cond)
+	  && !is_gimple_val (TREE_OPERAND (cond, 0)))
+	return false;
+      
+      if (TREE_CODE (cond) == TRUTH_NOT_EXPR
+          &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
+        return false;
+
+      new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+                    PHI_RESULT (phi), cond);
+    }
+  
+  /* Insert our new statement at the head of our block.  */
+  bsi = bsi_start (bb);
+  bsi_insert_after (&bsi, new, BSI_SAME_STMT);
+  
+  /* Register our new statement as the defining statement for
+      the result.  */
+  SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new;
+  
+  /* Remove the now useless PHI node. 
+  
+      We do not want to use remove_phi_node since that releases the
+      SSA_NAME as well and the SSA_NAME is still being used.  */
+  release_phi_node (phi);
+  bb_ann (bb)->phi_nodes = NULL;
+  
+  /* Disconnect the edge leading into the empty block.  That will
+     make the empty block unreachable and it will be removed later.  */
+  if (cond_block->succ->dest == bb)
+    {
+      cond_block->succ->flags |= EDGE_FALLTHRU;
+      cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+      ssa_remove_edge (cond_block->succ->succ_next);
+    }
+  else
+    {
+      cond_block->succ->succ_next->flags |= EDGE_FALLTHRU;
+      cond_block->succ->succ_next->flags
+	&= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+      ssa_remove_edge (cond_block->succ);
+    }
+  
+  /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
+  bsi = bsi_last (cond_block);
+  bsi_remove (&bsi);
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file,
+              "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
+              cond_block->index,
+              bb->index);
+            
+  /* Note that we optimized this PHI.  */
+  return true;
+}
+
+
+/* Always do these optimizations if we have SSA
+   trees to work on.  */						
+static bool
+gate_phiopt (void)
+{
+  return 1;
+}
+												
+struct tree_opt_pass pass_phiopt =
+{
+  "phiopt",				/* name */
+  gate_phiopt,				/* gate */
+  tree_ssa_phiopt,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_PHIOPT,			/* 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_flags_finish */
+    | TODO_verify_ssa
+};
+												
+