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] More improvements for the code generation of the if-conversion


Hi,

The attached patches clean the code generated by the if-conversion:

0001 adds a debug counter, useful to reduce code generation problems
due to the tree-if-conversion pass.

0002 calls the cleanup_tree_cfg after if-conversion to ensure that the
CFG representation passed to the vectorizer is in good shape.

0003 adds some more sanity checks after the if-conversion pass:
verify_loop_structure and verify_loop_closed_ssa.

0004 moves the code needed for the computation of the predicate of a
BB at the beginning of the predicated BB.  The computation of the
insertion place is simplified, and makes it possible to use this
predicate in the code of the BB.

0005 implements and calls an unfold SSA function that first expands
the SSA_NAMEs and then calls fold on the expanded expression tree.
unfold_ssa_names exposes to fold a more complete expression than
otherwise available in the predicates of a BB.  This patch is now
needed to improve the quality of the code generated by the
if-conversion as if-convert gimplifies the predicates in order to
avoid recomputations of some predicates.  With this patch it is
possible to fold (a || b) into the true predicate when a and b are the
predicates of the two branches of a condition, as the SSA_NAMEs a and
b are first unfolded into their respective expressions and then fold
finishes by computing the true predicate.  Note that this patch needs
some adjustment, i.e., replacing the magic constant 5 that is the
depth level for the unfold traversal to be some parameter, or so.

0006 uses a single function reset_bb_predicate to reset the predicate
of a BB to true.  This function has to release all the SSA_NAMEs used
in the gimplification of a predicate.

0007 avoids the generation of code computing the true predicate, that
occurs for all the BBs merging disjunct predicates leading to the true
predicate.

0008 forces the predicate of a BB to be either is_gimple_condexpr or
otherwise the predicate is gimplified, avoiding the insertion of the
same computation on other predicates.

This patch-set passed regstrap on amd64-linux with
BOOT_CFLAGS= -g -O3 -msse2.
Ok for trunk?

Thanks,
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools
From 31c0a11ffb70d2ce947cb9e39f10f0f79d1b23cc Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Thu, 22 Apr 2010 11:40:18 -0500
Subject: [PATCH 01/10] Add a debug counter for the tree-ssa level if-conversion.

	* Makefile.in (tree-if-conv.o): Depends on DBGCNT_H.
	* dbgcnt.def (if_conversion_tree): New DEBUG_COUNTER.
	* tree-if-conv.c: Include dbgcnt.h.
	(tree_if_conversion): Use if_conversion_tree to count the number of
	if-convertible loops.
---
 gcc/Makefile.in    |    2 +-
 gcc/dbgcnt.def     |    1 +
 gcc/tree-if-conv.c |    4 +++-
 3 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 98ed23d..03eb6da 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2500,7 +2500,7 @@ tree-nested.o: tree-nested.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) \
 tree-if-conv.o: tree-if-conv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) $(FLAGS_H) $(TIMEVAR_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
    $(CFGLOOP_H) $(TREE_DATA_REF_H) $(TREE_PASS_H) $(DIAGNOSTIC_H) \
-   $(TREE_DUMP_H) tree-pretty-print.h gimple-pretty-print.h
+   $(TREE_DUMP_H) $(DBGCNT_H) tree-pretty-print.h gimple-pretty-print.h
 tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
    coretypes.h $(GGC_H) tree-iterator.h $(GIMPLE_H) gt-tree-iterator.h
 tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index 33afb0b..0d73d94 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -160,6 +160,7 @@ DEBUG_COUNTER (global_alloc_at_reg)
 DEBUG_COUNTER (hoist)
 DEBUG_COUNTER (ia64_sched2)
 DEBUG_COUNTER (if_conversion)
+DEBUG_COUNTER (if_conversion_tree)
 DEBUG_COUNTER (if_after_combine)
 DEBUG_COUNTER (if_after_reload)
 DEBUG_COUNTER (local_alloc_for_sched)
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 1686473..b7fe749 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -98,6 +98,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
+#include "dbgcnt.h"
 
 /* List of basic blocks in if-conversion-suitable order.  */
 static basic_block *ifc_bbs;
@@ -1178,7 +1179,8 @@ tree_if_conversion (struct loop *loop)
 {
   ifc_bbs = NULL;
 
-  if (!if_convertible_loop_p (loop))
+  if (!if_convertible_loop_p (loop)
+      || !dbg_cnt (if_conversion_tree))
     goto cleanup;
 
   /* Now all statements are if-convertible.  Combine all the basic
-- 
1.7.0.4

From 6dbf7fd3679587c77d002faaeb233d706929b34f Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 14:57:01 -0500
Subject: [PATCH 02/10] Call cleanup_tree_cfg after if-conversion.

	* tree-if-conv.c (combine_blocks): Remove FIXME comment.
	(tree_if_conversion): Returns true when something has been changed.
	(main_tree_if_conversion): Call cleanup_tree_cfg when if-conversion
	changed something.
---
 gcc/tree-if-conv.c |   18 ++++++++++++------
 1 files changed, 12 insertions(+), 6 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index b7fe749..2fba064 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1162,9 +1162,7 @@ combine_blocks (struct loop *loop)
 
   /* If possible, merge loop header to the block with the exit edge.
      This reduces the number of basic blocks to two, to please the
-     vectorizer that handles only loops with two nodes.
-
-     FIXME: Call cleanup_tree_cfg.  */
+     vectorizer that handles only loops with two nodes.  */
   if (exit_bb
       && exit_bb != loop->header
       && can_merge_blocks_p (loop->header, exit_bb))
@@ -1172,11 +1170,12 @@ combine_blocks (struct loop *loop)
 }
 
 /* If-convert LOOP when it is legal.  For the moment this pass has no
-   profitability analysis.  */
+   profitability analysis.  Returns true when something changed.  */
 
-static void
+static bool
 tree_if_conversion (struct loop *loop)
 {
+  bool changed = false;
   ifc_bbs = NULL;
 
   if (!if_convertible_loop_p (loop)
@@ -1187,6 +1186,7 @@ tree_if_conversion (struct loop *loop)
      blocks into one huge basic block doing the if-conversion
      on-the-fly.  */
   combine_blocks (loop);
+  changed = true;
 
  cleanup:
   if (ifc_bbs)
@@ -1199,6 +1199,8 @@ tree_if_conversion (struct loop *loop)
       free (ifc_bbs);
       ifc_bbs = NULL;
     }
+
+  return changed;
 }
 
 /* Tree if-conversion pass management.  */
@@ -1208,12 +1210,16 @@ main_tree_if_conversion (void)
 {
   loop_iterator li;
   struct loop *loop;
+  bool changed = false;
 
   if (number_of_loops () <= 1)
     return 0;
 
   FOR_EACH_LOOP (li, loop, 0)
-    tree_if_conversion (loop);
+    changed |= tree_if_conversion (loop);
+
+  if (changed)
+    cleanup_tree_cfg ();
 
   return 0;
 }
-- 
1.7.0.4

From 0823348415990af18f5b7c46e09cdf8cd09135fe Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 15:21:10 -0500
Subject: [PATCH 03/10] Verify loops and closed SSA form after if-conversion.

	* tree-if-conv.c (main_tree_if_conversion): Call
	verify_loop_structure and verify_loop_closed_ssa after if-conversion.
---
 gcc/tree-if-conv.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 2fba064..16e0c48 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1221,6 +1221,11 @@ main_tree_if_conversion (void)
   if (changed)
     cleanup_tree_cfg ();
 
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+
   return 0;
 }
 
-- 
1.7.0.4

From b4e0ca3e1a5d821c72e9bca5dcd3ccc3193a4cd9 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 15 Jun 2010 15:19:40 -0500
Subject: [PATCH 04/10] Insert the gimplification of a predicate at the beginning of the predicated BB.

	* tree-if-conv.c (insert_gimplified_predicates): Insert the
	gimplification of a predicate at the beginning of the
	predicated BB.
---
 gcc/tree-if-conv.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 16e0c48..993b739 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1014,13 +1014,9 @@ insert_gimplified_predicates (loop_p loop)
 
       if (stmts)
 	{
-	  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+	  gimple_stmt_iterator gsi = gsi_after_labels (bb);
 
-	  if (gsi_end_p (gsi)
-	      || gimple_code (gsi_stmt (gsi)) == GIMPLE_COND)
-	    gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
-	  else
-	    gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
+	  gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
 
 	  /* Once the sequence is code generated, set it to NULL.  */
 	  set_bb_predicate_gimplified_stmts (bb, NULL);
-- 
1.7.0.4

From 7dd1fe9d133ec655d2d0d7c4f2b20f55fdea6421 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 12:00:51 -0500
Subject: [PATCH 05/10] Unfold the predicates to expose computations to fold.

	* fold-const.c (unfold_ssa_names): New.
	* tree.h (unfold_ssa_names): Declared.
	* tree-if-conv.c (is_predicated): Call unfold_ssa_names.
	(add_to_predicate_list): Call is_predicated.
---
 gcc/fold-const.c   |   83 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-if-conv.c |   21 +++++++++----
 gcc/tree.h         |    1 +
 3 files changed, 99 insertions(+), 6 deletions(-)

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 9f2c250..5c3ef16 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -15883,3 +15883,86 @@ fold_strip_sign_ops (tree exp)
     }
   return NULL_TREE;
 }
+
+/* Unfolds LEVEL times the SSA names in expression EXPR.  */
+
+tree
+unfold_ssa_names (tree expr, int level)
+{
+  tree type, op0, op1, op2;
+  enum tree_code code;
+  gimple stmt;
+
+  level--;
+
+  if (!expr || level < 0)
+    return expr;
+
+  code = TREE_CODE (expr);
+  switch (code)
+    {
+    case SSA_NAME:
+      stmt = SSA_NAME_DEF_STMT (expr);
+
+      if (gimple_code (stmt) != GIMPLE_ASSIGN)
+	return expr;
+
+      code = gimple_assign_rhs_code (stmt);
+
+      switch (code)
+	{
+	case INDIRECT_REF:
+	case ALIGN_INDIRECT_REF:
+	case MISALIGNED_INDIRECT_REF:
+	case REALPART_EXPR:
+	case IMAGPART_EXPR:
+	case ARRAY_REF:
+	case ARRAY_RANGE_REF:
+	case COMPONENT_REF:
+	case BIT_FIELD_REF:
+	  return expr;
+
+	default:
+	  break;
+	}
+
+      op1 = unfold_ssa_names (gimple_assign_rhs1 (stmt), level);
+      op2 = unfold_ssa_names (gimple_assign_rhs2 (stmt), level);
+      type = TREE_TYPE (gimple_assign_lhs (stmt));
+
+      switch (TREE_CODE_LENGTH (code))
+	{
+	case 2:
+	  return fold_build2 (code, type, op1, op2);
+
+	case 1:
+	  return fold_build1 (code, type, op1);
+
+	default:
+	  return expr;
+	}
+
+    default:
+      type = TREE_TYPE (expr);
+      switch (TREE_CODE_LENGTH (code))
+	{
+	case 3:
+	  op0 = unfold_ssa_names (TREE_OPERAND (expr, 0), level);
+	  op1 = unfold_ssa_names (TREE_OPERAND (expr, 1), level);
+	  op2 = unfold_ssa_names (TREE_OPERAND (expr, 2), level);
+	  return fold_build3 (code, type, op0, op1, op2);
+
+	case 2:
+	  op0 = unfold_ssa_names (TREE_OPERAND (expr, 0), level);
+	  op1 = unfold_ssa_names (TREE_OPERAND (expr, 1), level);
+	  return fold_build2 (code, type, op0, op1);
+
+	case 1:
+	  op0 = unfold_ssa_names (TREE_OPERAND (expr, 0), level);
+	  return fold_build1 (code, type, op0);
+
+	default:
+	  return expr;
+	}
+    }
+}
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 993b739..5b37654 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -246,7 +246,9 @@ is_true_predicate (tree cond)
 static inline bool
 is_predicated (basic_block bb)
 {
-  return !is_true_predicate (bb_predicate (bb));
+  tree cond = unfold_ssa_names (bb_predicate (bb), 5);
+
+  return !is_true_predicate (cond);
 }
 
 /* Add condition NEW_COND to the predicate list of basic block BB.  */
@@ -254,12 +256,19 @@ is_predicated (basic_block bb)
 static inline void
 add_to_predicate_list (basic_block bb, tree new_cond)
 {
-  tree cond = bb_predicate (bb);
+  tree cond;
+
+  if (!is_predicated (bb))
+    cond = new_cond;
+  else
+    {
+      cond = bb_predicate (bb);
+      cond = fold_build2_loc (EXPR_LOCATION (cond), TRUTH_OR_EXPR,
+			      boolean_type_node, cond, new_cond);
+      cond = unfold_ssa_names (cond, 5);
+    }
 
-  set_bb_predicate (bb, is_true_predicate (cond) ? new_cond :
-		    fold_build2_loc (EXPR_LOCATION (cond),
-				     TRUTH_OR_EXPR, boolean_type_node,
-				     cond, new_cond));
+  set_bb_predicate (bb, cond);
 }
 
 /* Add the condition COND to the previous condition PREV_COND, and add
diff --git a/gcc/tree.h b/gcc/tree.h
index 1a2ac3a..c2a36b1 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4957,6 +4957,7 @@ extern tree build_fold_addr_expr_loc (location_t, tree);
 extern tree build_fold_addr_expr_with_type_loc (location_t, tree, tree);
 extern tree fold_build_cleanup_point_expr (tree type, tree expr);
 extern tree fold_strip_sign_ops (tree);
+extern tree unfold_ssa_names (tree, int);
 #define build_fold_indirect_ref(T)\
         build_fold_indirect_ref_loc (UNKNOWN_LOCATION, T)
 extern tree build_fold_indirect_ref_loc (location_t, tree);
-- 
1.7.0.4

From 8c3bfd6ca12629a85d8a35b33671e2e448249e62 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 16:01:27 -0500
Subject: [PATCH 06/10] Use reset_bb_predicate whenever the predicate of a BB should be reset to true.

	* tree-if-conv.c (init_bb_predicate): Initialize the predicate
	to boolean_true_node.
	(reset_bb_predicate): New.
	(predicate_bbs): Call reset_bb_predicate.
---
 gcc/tree-if-conv.c |   17 +++++++++++++----
 1 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 5b37654..9e07cb3 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -175,7 +175,7 @@ init_bb_predicate (basic_block bb)
 {
   bb->aux = XNEW (struct bb_predicate_s);
   set_bb_predicate_gimplified_stmts (bb, NULL);
-  set_bb_predicate (bb, NULL_TREE);
+  set_bb_predicate (bb, boolean_true_node);
 }
 
 /* Free the predicate of basic block BB.  */
@@ -203,6 +203,16 @@ free_bb_predicate (basic_block bb)
   bb->aux = NULL;
 }
 
+/* Free the predicate of BB and reinitialize it with the true
+   predicate.  */
+
+static inline void
+reset_bb_predicate (basic_block bb)
+{
+  free_bb_predicate (bb);
+  init_bb_predicate (bb);
+}
+
 /* Create a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
    to the new variable.  */
 
@@ -614,8 +624,7 @@ predicate_bbs (loop_p loop)
 	 to be processed: skip it.  */
       if (bb == loop->latch)
 	{
-	  set_bb_predicate (loop->latch, boolean_true_node);
-	  set_bb_predicate_gimplified_stmts (loop->latch, NULL);
+	  reset_bb_predicate (loop->latch);
 	  continue;
 	}
 
@@ -689,7 +698,7 @@ predicate_bbs (loop_p loop)
     }
 
   /* The loop header is always executed.  */
-  set_bb_predicate (loop->header, boolean_true_node);
+  reset_bb_predicate (loop->header);
   gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
 	      && bb_predicate_gimplified_stmts (loop->latch) == NULL);
 
-- 
1.7.0.4

From 752c52f7093d69a87f99d2b0b3e67142f51c6d0f Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 15:17:26 -0500
Subject: [PATCH 07/10] Do not insert statements computing the true predicate.

	* tree-if-conv.c (insert_gimplified_predicates): Do not insert
	statements computing the true predicate.
---
 gcc/tree-if-conv.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 9e07cb3..ac3ba93 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1030,6 +1030,15 @@ insert_gimplified_predicates (loop_p loop)
       basic_block bb = ifc_bbs[i];
       gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
 
+      if (!is_predicated (bb))
+	{
+	  /* Do not insert statements for a basic block that is not
+	     predicated.  Also make sure that the predicate of the
+	     basic block is set to true.  */
+	  reset_bb_predicate (bb);
+	  continue;
+	}
+
       if (stmts)
 	{
 	  gimple_stmt_iterator gsi = gsi_after_labels (bb);
-- 
1.7.0.4

From 35f74eaa5d4a79f3fcdfeae8bdf3b81751c6f1ba Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Wed, 16 Jun 2010 15:57:53 -0500
Subject: [PATCH 08/10] The predicate of a BB should either be a gimple_condexpr or an SSA_NAME.

	* tree-if-conv.c (add_to_predicate_list): Call force_gimple_operand
	when the predicate is not a gimple_condexpr.  Call reset_bb_predicate
	when the predicate is true.

	* gcc.dg/tree-ssa/ifc-6.c: New.
---
 gcc/testsuite/gcc.dg/tree-ssa/ifc-6.c |   15 +++++++++++++++
 gcc/tree-if-conv.c                    |   12 +++++++++++-
 2 files changed, 26 insertions(+), 1 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-6.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-6.c
new file mode 100644
index 0000000..a9c5db3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-6.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -ftree-vectorize" { target *-*-* } } */
+
+static int x;
+foo (int n, int *A)
+{
+  int i;
+  for (i = 0; i < n; i++)
+    {
+      if (A[i])
+	x = 2;
+      if (A[i + 1])
+	x = 1;
+    }
+}
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index ac3ba93..759920c 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -278,7 +278,17 @@ add_to_predicate_list (basic_block bb, tree new_cond)
       cond = unfold_ssa_names (cond, 5);
     }
 
-  set_bb_predicate (bb, cond);
+  if (!is_gimple_condexpr (cond))
+    {
+      gimple_seq stmts;
+      cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
+      add_bb_predicate_gimplified_stmts (bb, stmts);
+    }
+
+  if (is_true_predicate (cond))
+    reset_bb_predicate (bb);
+  else
+    set_bb_predicate (bb, cond);
 }
 
 /* Add the condition COND to the previous condition PREV_COND, and add
-- 
1.7.0.4


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