This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Simple jump forwarding
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 22 Oct 2003 18:33:47 -0600
- Subject: [tree-ssa] Simple jump forwarding
- Reply-to: law at redhat dot com
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;