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] Allow merging blocks with phi nodes


Hello,

now that we have lists of immediate uses always available, it is
possible to effectively get rid of phi nodes between two merged
blocks (by copy propagating them).  This for example enables the
blocks created by loop unrolling to be merged immediatelly, rather
then waiting till the first copyprop + dce pass (that currently comes
much later).

Bootstrapped & regtested on i686.  There are few failures in vectorizer
testcases due to bugs in updating of virtual operands in vectorizer,
see http://gcc.gnu.org/ml/gcc-patches/2005-04/msg01810.html and
followups.

New version of fold_stmt (fold_stmt_inplace) is necessary, since
fold_stmt may replace the whole statement, but we cannot get the pointer
to statement from immediate uses, only the statement itself.

Zdenek

	* tree-cfg.c (tree_can_merge_blocks_p): Allow phi nodes in the
	merged block.
	(replace_uses_by): New function.
	(tree_merge_blocks): Eliminate the phi nodes in the merged block.
	* tree-flow.h (fold_stmt_inplace): Declare.
	* tree-ssa-ccp.c (fold_stmt_inplace): New function.
	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Update dominance
	info after cfg cleanup.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.189
diff -c -3 -p -r2.189 tree-cfg.c
*** tree-cfg.c	14 May 2005 14:24:47 -0000	2.189
--- tree-cfg.c	16 May 2005 14:04:19 -0000
*************** tree_can_merge_blocks_p (basic_block a, 
*** 1261,1266 ****
--- 1261,1267 ----
  {
    tree stmt;
    block_stmt_iterator bsi;
+   tree phi;
  
    if (!single_succ_p (a))
      return false;
*************** tree_can_merge_blocks_p (basic_block a, 
*** 1288,1296 ****
        && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
      return false;
  
!   /* There may be no PHI nodes at the start of B.  */
!   if (phi_nodes (b))
!     return false;
  
    /* Do not remove user labels.  */
    for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
--- 1289,1307 ----
        && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
      return false;
  
!   /* It must be possible to eliminate all phi nodes in B.  If ssa form
!      is not up-to-date, we cannot eliminate any phis.  */
!   phi = phi_nodes (b);
!   if (phi)
!     {
!       if (need_ssa_update_p ())
! 	return false;
! 
!       for (; phi; phi = PHI_CHAIN (phi))
! 	if (!is_gimple_reg (PHI_RESULT (phi))
! 	    && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
! 	  return false;
!     }
  
    /* Do not remove user labels.  */
    for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
*************** tree_can_merge_blocks_p (basic_block a, 
*** 1310,1315 ****
--- 1321,1375 ----
    return true;
  }
  
+ /* Replaces all uses of NAME by VAL.  */
+ 
+ static void
+ replace_uses_by (tree name, tree val)
+ {
+   imm_use_iterator imm_iter;
+   use_operand_p use;
+   tree stmt;
+   edge e;
+   unsigned i;
+   VEC(tree,heap) *stmts = VEC_alloc (tree, heap, 20);
+ 
+   FOR_EACH_IMM_USE_SAFE (use, imm_iter, name)
+     {
+       stmt = USE_STMT (use);
+ 
+       SET_USE (use, val);
+ 
+       if (TREE_CODE (stmt) == PHI_NODE)
+ 	{
+ 	  e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
+ 	  if (e->flags & EDGE_ABNORMAL)
+ 	    {
+ 	      /* This can only occur for virtual operands, since
+ 		 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+ 		 would prevent replacement.  */
+ 	      gcc_assert (!is_gimple_reg (name));
+ 	      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
+ 	    }
+ 	}
+       else
+ 	VEC_safe_push (tree, heap, stmts, stmt);
+     }
+  
+   /* We do not update the statements in the loop above.  Consider
+      x = w * w;
+ 
+      If we performed the update in the first loop, the statement
+      would be rescanned after first occurence of w is replaced,
+      the new uses would be placed to the beginning of the list,
+      and we would never process them.  */
+   for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++)
+     {
+       fold_stmt_inplace (stmt);
+       update_stmt (stmt);
+     }
+ 
+   VEC_free (tree, heap, stmts);
+ }
  
  /* Merge block B into block A.  */
  
*************** tree_merge_blocks (basic_block a, basic_
*** 1318,1327 ****
--- 1378,1417 ----
  {
    block_stmt_iterator bsi;
    tree_stmt_iterator last;
+   tree phi;
  
    if (dump_file)
      fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
  
+   /* Remove the phi nodes.  */
+   bsi = bsi_last (a);
+   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
+     {
+       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
+       tree copy;
+       
+       if (!may_propagate_copy (def, use)
+ 	  /* Propagating pointers might cause the set of vops for statements
+ 	     to be changed, and thus require ssa form update.  */
+ 	  || (is_gimple_reg (def)
+ 	      && POINTER_TYPE_P (TREE_TYPE (def))))
+ 	{
+ 	  gcc_assert (is_gimple_reg (def));
+ 
+ 	  /* Note that just emiting the copies is fine -- there is no problem
+ 	     with ordering of phi nodes.  This is because A is the single
+ 	     predecessor of B, therefore results of the phi nodes cannot
+ 	     appear as arguments of the phi nodes.  */
+ 	  copy = build2 (MODIFY_EXPR, void_type_node, def, use);
+ 	  bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
+ 	  SET_PHI_RESULT (phi, NULL_TREE);
+ 	  SSA_NAME_DEF_STMT (def) = copy;
+ 	}
+       else
+ 	replace_uses_by (def, use);
+       remove_phi_node (phi, NULL);
+     }
+ 
    /* Ensure that B follows A.  */
    move_block_after (b, a);
  

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.104
diff -c -3 -p -r2.104 tree-flow.h
*** tree-flow.h	12 May 2005 22:32:16 -0000	2.104
--- tree-flow.h	16 May 2005 14:04:19 -0000
*************** void set_current_def (tree, tree);
*** 629,634 ****
--- 629,635 ----
  
  /* In tree-ssa-ccp.c  */
  bool fold_stmt (tree *);
+ bool fold_stmt_inplace (tree);
  tree widen_bitfield (tree, tree, tree);
  
  /* In tree-vrp.c  */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.70
diff -c -3 -p -r2.70 tree-ssa-ccp.c
*** tree-ssa-ccp.c	8 May 2005 21:22:20 -0000	2.70
--- tree-ssa-ccp.c	16 May 2005 14:04:19 -0000
*************** fold_stmt (tree *stmt_p)
*** 2308,2313 ****
--- 2308,2339 ----
    return changed;
  }
  
+ /* Perform the minimal folding on statement STMT.  Only operations like
+    *&x created by constant propagation are handled.  The statement cannot
+    be replaced with a new one.  */
+ 
+ bool
+ fold_stmt_inplace (tree stmt)
+ {
+   tree old_stmt = stmt, rhs, new_rhs;
+   bool changed = false;
+ 
+   walk_tree (&stmt, fold_stmt_r, &changed, NULL);
+   gcc_assert (stmt == old_stmt);
+ 
+   rhs = get_rhs (stmt);
+   if (!rhs || rhs == stmt)
+     return changed;
+ 
+   new_rhs = fold (rhs);
+   if (new_rhs == rhs)
+     return changed;
+ 
+   changed |= set_rhs (&stmt, new_rhs);
+   gcc_assert (stmt == old_stmt);
+ 
+   return changed;
+ }
  
  /* Convert EXPR into a GIMPLE value suitable for substitution on the
     RHS of an assignment.  Insert the necessary statements before
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.110
diff -c -3 -p -r2.110 tree-ssa-dom.c
*** tree-ssa-dom.c	10 May 2005 20:21:27 -0000	2.110
--- tree-ssa-dom.c	16 May 2005 14:04:19 -0000
*************** tree_ssa_dominator_optimize (void)
*** 404,409 ****
--- 404,410 ----
    /* Clean up the CFG so that any forwarder blocks created by loop
       canonicalization are removed.  */
    cleanup_tree_cfg ();
+   calculate_dominance_info (CDI_DOMINATORS);
  
    /* If we prove certain blocks are unreachable, then we want to
       repeat the dominator optimization process as PHI nodes may


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