This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] add abs transformation to tree-ssa-phiopt


Now that optimization/14673 is fixed, I can submit this patch which
adds abs transformation to tree-ssa-phiopt.

I see a couple transformations in eon from SPEC but did not time it
at all (this is with -ffast-math).


OK? Bootstrapped on powerpc-apple-darwin7.3.0 with no regressions.



Testcase which should describe everything: /* { dg-do compile } */ /* { dg-options "-O1 -fdump-tree-phiopt1-details" } */

int t( int i)
{
  int j;
  if(i>=0)
   j = i;
  else
   j = -i;
  return j;
}

/* We should convert one COND_EXPRs into straightline code with ABS.  */
/* { dg-final { scan-tree-dump-times "straightline" 1 "phiopt1"} } */
/* { dg-final { scan-tree-dump-times "ABS_EXPR" 1 "phiopt1"} } */


ChangeLog:


	* tree-ssa-phiopt.c (absolute_replacement): New function.
	(tree_ssa_phiopt): Call it.


Patch:
Index: tree-ssa-phiopt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-phiopt.c,v
retrieving revision 2.2
diff -u -p -b -r2.2 tree-ssa-phiopt.c
--- tree-ssa-phiopt.c 14 May 2004 15:27:36 -0000 2.2
+++ tree-ssa-phiopt.c 14 May 2004 21:21:59 -0000
@@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - S
#include "errors.h"
#include "ggc.h"
#include "tree.h"
+#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "basic-block.h"
@@ -39,6 +40,9 @@ static void tree_ssa_phiopt (void);
static bool conditional_replacement (basic_block bb, tree phi, tree arg0,
tree arg1);


+static bool absolute_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:
@@ -58,7 +62,29 @@ static bool conditional_replacement (bas


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. */
+ of conditionals.
+
+ Also this pass eliminates PHI nodes which are really absolute values. ie
+ if we have something like:
+
+ bb0:
+ if (a >= 0) goto bb2; else goto bb1;
+ bb1:
+ x = -a;
+ bb2:
+ x = PHI (x (bb1), a (bb0));
+
+ We can rewrite that as:
+
+ bb0:
+ bb1:
+ bb2:
+ x = ABS_EXPR< a >;
+
+ bb1 will become unreachable and bb0 and bb2 will almost always be merged
+ into a single block. This occurs because fold never had dected then in
+ the first place, note some of this is all done already by the ifcvt
+ optimization on the RTL level. */


static void
tree_ssa_phiopt (void)
@@ -85,7 +111,16 @@ tree_ssa_phiopt (void)
/* 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. */
+ /* We have done the replacement so we need to rebuild the
+ cfg and cannot do any more. */
+ removed_phis = true;
+ continue;
+ }
+ /* Do the replacement for absolute if it can be done. */
+ if (absolute_replacement (bb, phi, arg0, arg1))
+ {
+ /* We have done the replacement so we need to rebuild the
+ cfg and cannot do any more. */
removed_phis = true;
continue;
}
@@ -316,6 +351,316 @@ conditional_replacement (basic_block bb,
return true;
}


+
+/* The function absolute_replacement does the main work of doing the absolute
+ 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
+absolute_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;
+ tree asign = NULL;
+ bool arg0_neg = false;
+ bool isAbs = true;
+ tree variable;
+
+
+ /* One of the alternatives must come from a block ending with
+ a COND_EXPR. The other block must be only a statement with
+ an assignment of a variable of -arg0 or -arg1. */
+ 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;
+ }
+ 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 only one executable statement, the assignment. */
+ bsi = bsi_start (other_block);
+ while (!bsi_end_p (bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ if (TREE_CODE (stmt) == LABEL_EXPR
+ || IS_EMPTY_STMT (stmt))
+ {
+ bsi_next (&bsi);
+ continue;
+ }
+ /* Is this the assignment */
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree stmt_arg0 = TREE_OPERAND (stmt, 0);
+ tree stmt_arg1 = TREE_OPERAND (stmt, 1);
+ if (TREE_CODE (stmt_arg1) == NEGATE_EXPR)
+ {
+ stmt_arg1 = TREE_OPERAND (stmt_arg1, 0);
+ /* The assignment has to be arg0 = arg1 or arg1 = arg0. */
+ /* FIXME: Handle more complex cases like arg1 = a-b and before
+ the conditional arg0 = b-a; */
+ if (stmt_arg0 == arg0 && stmt_arg1 == arg1)
+ {
+ asign = stmt;
+ arg0_neg = false;
+ break;
+ }
+ if (stmt_arg0 == arg1 && stmt_arg1 == arg0)
+ {
+ asign = stmt;
+ arg0_neg = true;
+ break;
+ }
+ }
+ }
+ return false;
+ }
+
+ /* We did not find an assignment so we cannot do the replacement. */
+ if (asign == NULL)
+ return false;
+
+
+ /* The rest of the OTHER_BLOCK should be empty. */
+ bsi_next (&bsi);
+ while (!bsi_end_p (bsi)
+ && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
+ || IS_EMPTY_STMT (bsi_stmt (bsi))))
+ bsi_next (&bsi);
+
+ /* There was some other expression in the basic block
+ so this optimization cannot be done. */
+ if (!bsi_end_p (bsi))
+ return false;
+
+ cond = COND_EXPR_COND (last_stmt (cond_block));
+ result = PHI_RESULT (phi);
+
+ /* We need to know which is the true edge and which is the false
+ edge so that we know if have abs or negative abs. */
+ extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
+
+ /* Only less than, greater than, and those with "and equal" to them
+ are the ones which are needed for abs/nabs. */
+ switch (TREE_CODE (cond))
+ {
+ case LT_EXPR:
+ case LE_EXPR:
+ {
+ if (arg0_neg)
+ {
+ /* FIXME: Handle all these cases. */
+ if (PHI_ARG_EDGE (phi, 0) == true_edge)
+ return false;
+
+ /* This is the case where arg0 is the variable
+ which is negatived and is the variable on
+ the false edge so it can be converted into
+ an nabs. */
+ else if (PHI_ARG_EDGE (phi, 0) == false_edge)
+ {
+ isAbs = true;
+ }
+ else if (PHI_ARG_EDGE (phi, 1) == false_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 1) == true_edge)
+ return false;
+ }
+ else
+ {
+ /* FIXME: Handle all these cases. */
+ if (PHI_ARG_EDGE (phi, 0) == true_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 0) == false_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 1) == false_edge)
+ return false;
+
+ /* This is the case where arg1 is the variable
+ which is negatived and is the variable on
+ the true edge so it can be converted into
+ an nabs. */
+ else if (PHI_ARG_EDGE (phi, 1) == true_edge)
+ {
+ isAbs = false;
+ }
+ }
+ break;
+ }
+ case GT_EXPR:
+ case GE_EXPR:
+ {
+ if (arg0_neg)
+ {
+ /* FIXME: Handle all these cases. */
+ if (PHI_ARG_EDGE (phi, 0) == true_edge)
+ return false;
+
+ /* This is the case where arg0 is the variable
+ which is negatived and is the variable on
+ the false edge so it can be converted into
+ an nabs. */
+ else if (PHI_ARG_EDGE (phi, 0) == false_edge)
+ {
+ isAbs = false;
+ }
+ else if (PHI_ARG_EDGE (phi, 1) == false_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 1) == true_edge)
+ return false;
+ }
+ else
+ {
+ /* FIXME: Handle all these cases. */
+ if (PHI_ARG_EDGE (phi, 0) == true_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 0) == false_edge)
+ return false;
+ else if (PHI_ARG_EDGE (phi, 1) == false_edge)
+ return false;
+
+ /* This is the case where arg1 is the variable
+ which is negatived and is the variable on
+ the true edge so it can be converted into
+ an abs. */
+ else if (PHI_ARG_EDGE (phi, 1) == true_edge)
+ {
+ isAbs = true;
+ }
+ }
+ break;
+ }
+ default:
+ return false;
+ }
+
+
+ /* Make sure the conditional is arg[01] OP y. */
+
+ if (TREE_OPERAND (cond, 0) != (arg0_neg ? arg0 : arg1))
+ return false;
+
+ /* If the type says honor signed zeros we cannot do this
+ optimization. */
+ if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
+ return false;
+
+ /* Make sure that the arg[01] is comparing against 0. */
+ if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
+ ? real_zerop (TREE_OPERAND (cond, 1))
+ : integer_zerop (TREE_OPERAND (cond, 1)))
+ ;
+ else
+ return false;
+
+
+
+ result = PHI_RESULT (phi);
+ /* Make a new variable to hold the abs if need be. */
+ if (!isAbs)
+ variable = make_rename_temp (TREE_TYPE (result));
+ else
+ variable = result;
+
+
+ /* Build the modify expression with abs expression. */
+ new = build (MODIFY_EXPR, TREE_TYPE (variable),
+ variable, build1 (ABS_EXPR, TREE_TYPE (variable),
+ arg0_neg ? arg0 : arg1));
+
+ /* Insert our new statement at the head of our block. */
+ bsi = bsi_start (bb);
+ bsi_insert_after (&bsi, new, BSI_NEW_STMT);
+
+ if (!isAbs)
+ {
+ new = build (MODIFY_EXPR, TREE_TYPE (result),
+ result, build1 (NEGATE_EXPR, TREE_TYPE (variable),
+ variable));
+
+ bsi_insert_after (&bsi, new, BSI_NEW_STMT);
+ }
+
+ /* Register our new statement as the defining statement for
+ the result. */
+ SSA_NAME_DEF_STMT (result) = 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 (using ABS).\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.  */						

Attachment: abs.diff.txt
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]