[patch] Improve basic block merging

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Sat Nov 11 23:07:00 GMT 2006


Hello,

when there are phi nodes in the merged block and there are operands
are marked for renaming, basic block merging fails (to avoid generating
possibly wrong code by eliminating these phi nodes, if ssa form is not
consistent).  However, even if there are no operands marked for renaming
before cfg cleanup, eliminating the phi nodes (by copy/constant
propagation) during basic block merging sometimes causes new virtual
operands to appear on statements, which then prevents further merging
of blocks.  Such unmerged blocks then remain in cfg till the next cfg
cleanup, possibly several times.

This behavior is overly conservative.  If only symbols are marked for
renaming (not ssa names), then eliminating the phi nodes is still
safe (as the phi nodes for the affected symbols are ignored during
ssa update, anyway).

In fact, we could check whether the ssa names in the eliminated phi node
are affected by ssa update, and if not, we could proceed anyway;
nevertheless, I do not think this ever happens, so the patch just
makes us allow to eliminate the phi nodes even when symbols are marked
for renaming.

Bootstrapped & regtested on i686.

Zdenek

	* tree-flow.h (non_symbol_need_ssa_update_p): Declare.
	* tree-into-ssa.c (non_symbol_need_ssa_update_p): New function.
	* tree-cfg.c (tree_can_merge_blocks_p): Check
	non_symbol_need_ssa_update_p instead of need_ssa_update_p.

Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 118690)
--- tree-flow.h	(working copy)
*************** void delete_update_ssa (void);
*** 716,721 ****
--- 716,722 ----
  void register_new_name_mapping (tree, tree);
  tree create_new_def_for (tree, tree, def_operand_p);
  bool need_ssa_update_p (void);
+ bool non_symbol_need_ssa_update_p (void);
  bool name_registered_for_update_p (tree);
  bitmap ssa_names_to_replace (void);
  void release_ssa_name_after_update_ssa (tree name);
Index: tree-into-ssa.c
===================================================================
*** tree-into-ssa.c	(revision 118690)
--- tree-into-ssa.c	(working copy)
*************** need_ssa_update_p (void)
*** 2659,2664 ****
--- 2659,2671 ----
    return syms_to_rename || old_ssa_names || new_ssa_names;
  }
  
+ /* Return true if any non-symbol is registered for ssa updating.  */
+ 
+ bool
+ non_symbol_need_ssa_update_p (void)
+ {
+   return repl_tbl && htab_elements (repl_tbl) > 0;
+ }
  
  /* Return true if name N has been registered in the replacement table.  */
  
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 118690)
--- tree-cfg.c	(working copy)
*************** tree_can_merge_blocks_p (basic_block a, 
*** 1200,1210 ****
      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))
--- 1200,1212 ----
      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; however, if only
!      some symbols as whole are marked for renaming, this is not a problem,
!      as phi nodes for those symbols are irrelevant in updating anyway.  */
    phi = phi_nodes (b);
    if (phi)
      {
!       if (non_symbol_need_ssa_update_p ())
  	return false;
  
        for (; phi; phi = PHI_CHAIN (phi))
*************** replace_uses_by (tree name, tree val)
*** 1242,1248 ****
    edge e;
    unsigned i;
  
- 
    FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
      {
        FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
--- 1244,1249 ----



More information about the Gcc-patches mailing list