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]

[tree-ssa] Simple jump forwarding


This is not as extensive as Zdenek's patch for unconditional jump
threading.  When the COND_EXPR lowering code goes in it'll certainly
need to be extended to cover the cases Zdenek's patch covered, and I
think we can do so without major difficulties (and in a more readable
fashion then Zdenek's code).

Until then, it's badly needed to clean up lameness in the cfg.

	* tree-cfg.c (thread_unconditional_jumps): New function.
	(tree_block_forwards_to): Likewise.
	(cleanup_tree_cfg): Call thread_unconditional_jumps.
	* tree-flow.h (bb_ann_t): Add forwardable status bit.


Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.181
diff -c -3 -p -r1.1.4.181 tree-cfg.c
*** tree-cfg.c	20 Oct 2003 14:02:08 -0000	1.1.4.181
--- tree-cfg.c	22 Oct 2003 23:15:39 -0000
*************** static void remove_stmt (tree *, bool);
*** 137,142 ****
--- 137,144 ----
  static bool blocks_unreachable_p (bitmap);
  static void remove_blocks (bitmap);
  static void cleanup_control_flow (void);
+ static void thread_unconditional_jumps (void);
+ static basic_block tree_block_forwards_to (basic_block bb);
  static bool disconnect_unreachable_case_labels (basic_block, tree);
  static edge find_taken_edge_cond_expr (basic_block, tree);
  static edge find_taken_edge_switch_expr (basic_block, tree);
*************** cleanup_tree_cfg (void)
*** 1228,1233 ****
--- 1230,1236 ----
    timevar_push (TV_TREE_CLEANUP_CFG);
    pdom_info = NULL;
  
+   thread_unconditional_jumps ();
    cleanup_control_flow ();
    remove_unreachable_blocks ();
    linearize_control_structures ();
*************** remove_stmt (tree *stmt_p, bool remove_a
*** 2137,2142 ****
--- 2140,2295 ----
      bb->end_tree_p = stmt_p;
  }
  
+ /* Examine BB to determine if it is a forwarding block (a block which only
+    transfers control to a new destination).  If BB is a forwarding block,
+    then return the ultimate destination.  */
+ 
+ static basic_block
+ tree_block_forwards_to (basic_block bb)
+ {
+   block_stmt_iterator bsi;
+   bb_ann_t ann = bb_ann (bb);
+ 
+   /* If this block is not forwardable, then avoid useless work.  */
+   if (! ann->forwardable)
+     return NULL;
+ 
+   /* Set this block to not be forwardable.  This prevents infinite loops since
+      any block currently under examination is considered non-forwardable.  */
+   ann->forwardable = 0;
+ 
+   /* No forwarding is possible if this block is a special block (ENTRY/EXIT),
+      this block has more than one successor, this block's single successor is
+      reached via an abnormal edge, this block has phi nodes, or this block's
+      single successor has phi nodes.  */
+   if (bb == EXIT_BLOCK_PTR
+       || bb == ENTRY_BLOCK_PTR
+       || !bb->succ
+       || bb->succ->succ_next
+       || bb->succ->dest == EXIT_BLOCK_PTR
+       || (bb->succ->flags & EDGE_ABNORMAL) != 0
+       || phi_nodes (bb)
+       || phi_nodes (bb->succ->dest))
+     return NULL;
+ 
+   /* Walk past any labels or empty statements at the start of this block.  */
+   bsi = bsi_start (bb);
+   while (! bsi_end_p (bsi)
+ 	 && (IS_EMPTY_STMT (bsi_stmt (bsi))
+ 	     || TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR))
+     bsi_next (&bsi);
+ 
+   /* If we reached the end of this block, or hit a GOTO_EXPR to an known
+      location, then we may be able to optimize this case.  */
+   if (bsi_end_p (bsi)
+       || (bsi_stmt (bsi)
+ 	  && TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR
+ 	  && TREE_CODE (GOTO_DESTINATION (bsi_stmt (bsi))) == LABEL_DECL))
+     {
+       basic_block dest;
+ 
+       /* Recursive call to pick up chains of forwarding blocks.  */
+       dest = tree_block_forwards_to (bb->succ->dest);
+       if (dest)
+ 	{
+ 	  ann->forwardable = 1;
+ 	  return dest;
+ 	}
+ 
+       /* If we hit the end of the block, then we may need to insert a label
+ 	 at this block's destination.  */
+       if (bsi_end_p (bsi))
+ 	{
+ 	  tree stmt;
+ 
+ 	  bsi = bsi_start (bb->succ->dest);
+ 
+ 	  /* It's not clear if we can safely insert the label in this case.  */
+           if (bsi_end_p (bsi))
+ 	    return NULL;
+ 
+ 	  /* This really should not be necessary, but inserting a goto label
+ 	     before a case label can cause bogus error messages.  */
+ 	  stmt = bsi_stmt (bsi);
+ 	  if (TREE_CODE (stmt) == CASE_LABEL_EXPR)
+ 	    return NULL;
+ 
+ 	  /* If our new destination does not start with a label,
+ 	     then add one.  */
+ 	  if (TREE_CODE (stmt) != LABEL_EXPR)
+ 	    {
+ 	      /* DEST does not start with a label, add one.  */
+ 	      stmt = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+ 	      DECL_CONTEXT (stmt) = current_function_decl;
+ 	      stmt = build1 (LABEL_EXPR, void_type_node, stmt);
+ 	      bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+ 	    }
+ 	}
+ 
+       /* This block forwards to bb->succ->dest.  */
+       ann->forwardable = 1;
+       return bb->succ->dest;
+     }
+ 
+   /* No forwarding possible.  */
+   return NULL;
+ }
+ 
+ /* Try to thread any unconditional jumps through any forwarder blocks
+    (blocks which do nothing except jump somewhere else) to an ultimate
+    destination.  */
+ 
+ static void
+ thread_unconditional_jumps (void)
+ {
+   basic_block bb;
+ 
+   FOR_EACH_BB (bb)
+     bb_ann (bb)->forwardable = 1;
+ 
+   FOR_EACH_BB (bb)
+     {
+       /* Find blocks with a single successor which is not reached via an
+ 	 abnormal edge.  */
+       if (bb->succ
+ 	  && bb->succ->succ_next == NULL
+ 	  && (bb->succ->flags & EDGE_ABNORMAL) == 0)
+ 	{
+ 	  tree last = last_stmt (bb);
+ 
+ 	  /* See if our block ends with an unconditional jump.  */
+ 	  if (last
+ 	      && TREE_CODE (last) == GOTO_EXPR
+ 	      && TREE_CODE (GOTO_DESTINATION (last)) == LABEL_DECL)
+ 	    {
+ 	      basic_block dest;
+ 
+ 	      /* See if the target of our jump is a forwarding block.  */
+ 	      dest = tree_block_forwards_to (bb->succ->dest);
+ 	      if (dest)
+ 		{
+ 		  block_stmt_iterator bsi;
+ 		  tree label_stmt = NULL;
+ 
+ 		  /* Find the label at the start of the final destination.  */
+ 		  for (bsi = bsi_start (dest);
+ 		       ! bsi_end_p (bsi);
+ 		       bsi_next (&bsi))
+ 		    {
+ 		      label_stmt = bsi_stmt (bsi);
+ 
+ 		      if (TREE_CODE (label_stmt) == LABEL_EXPR)
+ 			break;
+ 		    }
+ 		  
+ 		  /* Update our GOTO_EXPR and the CFG.  */
+ 		  GOTO_DESTINATION (last) = LABEL_EXPR_LABEL (label_stmt);
+ 		  redirect_edge_succ (bb->succ, dest);
+ 		}
+ 	    }
+ 	}
+     }
+ }
  
  /* Try to remove superfluous control structures.  */
  
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.131
diff -c -3 -p -r1.1.4.131 tree-flow.h
*** tree-flow.h	18 Oct 2003 18:58:41 -0000	1.1.4.131
--- tree-flow.h	22 Oct 2003 23:15:39 -0000
*************** struct bb_ann_d
*** 312,317 ****
--- 312,321 ----
  
    /* Set of blocks immediately dominated by this node.  */
    bitmap dom_children;
+ 
+   /* Nonzero if this block is forwardable during cfg cleanups.  This is also
+      used to detect loops during cfg cleanups.  */
+   unsigned forwardable: 1;
  };
  
  typedef struct bb_ann_d *bb_ann_t;



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