This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] Move predictions list out of basic block
Hello,
> I wonder why we don't have a tree_bb_info struct like we have
> rtl_bb_info - the phi_nodes pointer would fit there as well as
> the stmt_list?
here is the patch that implements the idea, bootstrapped & regtested on
i686. Memory-wise, it probably won't save much (as function bodies are
stored in gimple), though.
It would be possible to really save the two pointers by letting
il.tree point to the list of stmts in block, and having phi nodes
stored in TREE_CHAIN field of the list of statements. It is a bit
hacky idea, though.
> Also can we get at the loop_depth via loop_father?
Not necessarily, loops are not present all the time. However,
loop_depth field is almost unused, so it should be possible to move it
away from bb.
> Also gcov count and frequency look like duplicated information.
Execept for possible slowdowns, I think it would be possible to
keep just counts (and remember the maximum count of a block in a
function in cfun). But I am sure Honza considered this and from
some reason (maybe the slowdowns?) it is not possible?
Zdenek
* tree-phinodes.c (reserve_phi_args_for_new_edge, remove_phi_node):
Use phi_nodes_ptr.
(create_phi_node): Use set_phi_nodes.
* omp-low.c (expand_omp_parallel): Use bb_stmt_list.
* tree-if-conv.c (process_phi_nodes): Use set_phi_nodes.
(combine_blocks): Use bb_stmt_list and set_bb_stmt_list.
* tree-flow-inline.h (phi_nodes, set_phi_nodes,
(bsi_start, bsi_last): Use bb_stmt_list.
(phi_nodes_ptr, bb_stmt_list, set_bb_stmt_list): New functions.
* cfgexpand.c (expand_gimple_basic_block): Use bb_stmt_list.
Traverse the statements using tsi iterator.
* basic-block.h (struct basic_block_def): Fields stmt_list
and phi_nodes moved to ...
(struct tree_bb_info): ... new structure.
* tree-cfg.c (create_bb): Allocate il.tree. Use set_bb_stmt_list.
(tree_merge_blocks): Use bb_stmt_list and set_bb_stmt_list.
(remove_bb): Handle blocks with NULL stmt list. Clear il.tree field.
(tree_verify_flow_info): Verify that il.tree is not set for
entry and exit block.
(tree_split_block): Use set_bb_stmt_list.
Index: tree-phinodes.c
===================================================================
*** tree-phinodes.c (revision 124042)
--- tree-phinodes.c (working copy)
*************** reserve_phi_args_for_new_edge (basic_blo
*** 313,319 ****
int len = EDGE_COUNT (bb->preds);
int cap = ideal_phi_node_len (len + 4);
! for (loc = &(bb->phi_nodes);
*loc;
loc = &PHI_CHAIN (*loc))
{
--- 313,319 ----
int len = EDGE_COUNT (bb->preds);
int cap = ideal_phi_node_len (len + 4);
! for (loc = phi_nodes_ptr (bb);
*loc;
loc = &PHI_CHAIN (*loc))
{
*************** create_phi_node (tree var, basic_block b
*** 354,360 ****
/* Add the new PHI node to the list of PHI nodes for block BB. */
PHI_CHAIN (phi) = phi_nodes (bb);
! bb->phi_nodes = phi;
/* Associate BB to the PHI node. */
set_bb_for_stmt (phi, bb);
--- 354,360 ----
/* Add the new PHI node to the list of PHI nodes for block BB. */
PHI_CHAIN (phi) = phi_nodes (bb);
! set_phi_nodes (bb, phi);
/* Associate BB to the PHI node. */
set_bb_for_stmt (phi, bb);
*************** remove_phi_node (tree phi, tree prev, bo
*** 458,464 ****
}
else
{
! for (loc = &(bb_for_stmt (phi)->phi_nodes);
*loc != phi;
loc = &PHI_CHAIN (*loc))
;
--- 458,464 ----
}
else
{
! for (loc = phi_nodes_ptr (bb_for_stmt (phi));
*loc != phi;
loc = &PHI_CHAIN (*loc))
;
Index: omp-low.c
===================================================================
*** omp-low.c (revision 124042)
--- omp-low.c (working copy)
*************** expand_omp_parallel (struct omp_region *
*** 2495,2501 ****
/* Declare local variables needed in CHILD_CFUN. */
block = DECL_INITIAL (child_fn);
BLOCK_VARS (block) = list2chain (child_cfun->unexpanded_var_list);
! DECL_SAVED_TREE (child_fn) = single_succ (entry_bb)->stmt_list;
/* Reset DECL_CONTEXT on locals and function arguments. */
for (t = BLOCK_VARS (block); t; t = TREE_CHAIN (t))
--- 2495,2501 ----
/* Declare local variables needed in CHILD_CFUN. */
block = DECL_INITIAL (child_fn);
BLOCK_VARS (block) = list2chain (child_cfun->unexpanded_var_list);
! DECL_SAVED_TREE (child_fn) = bb_stmt_list (single_succ (entry_bb));
/* Reset DECL_CONTEXT on locals and function arguments. */
for (t = BLOCK_VARS (block); t; t = TREE_CHAIN (t))
Index: tree-if-conv.c
===================================================================
*** tree-if-conv.c (revision 124042)
--- tree-if-conv.c (working copy)
*************** process_phi_nodes (struct loop *loop)
*** 865,871 ****
release_phi_node (phi);
phi = next;
}
! bb->phi_nodes = NULL;
}
return;
}
--- 865,871 ----
release_phi_node (phi);
phi = next;
}
! set_phi_nodes (bb, NULL_TREE);
}
return;
}
*************** combine_blocks (struct loop *loop)
*** 960,968 ****
}
/* Update stmt list. */
! last = tsi_last (merge_target_bb->stmt_list);
! tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
! bb->stmt_list = alloc_stmt_list ();
delete_basic_block (bb);
}
--- 960,968 ----
}
/* Update stmt list. */
! last = tsi_last (bb_stmt_list (merge_target_bb));
! tsi_link_after (&last, bb_stmt_list (bb), TSI_NEW_STMT);
! set_bb_stmt_list (bb, NULL);
delete_basic_block (bb);
}
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h (revision 124042)
--- tree-flow-inline.h (working copy)
*************** addresses_taken (tree stmt)
*** 637,643 ****
static inline tree
phi_nodes (basic_block bb)
{
! return bb->phi_nodes;
}
/* Set list of phi nodes of a basic block BB to L. */
--- 637,655 ----
static inline tree
phi_nodes (basic_block bb)
{
! gcc_assert (!(bb->flags & BB_RTL));
! if (!bb->il.tree)
! return NULL;
! return bb->il.tree->phi_nodes;
! }
!
! /* Return pointer to the list of PHI nodes for basic block BB. */
!
! static inline tree *
! phi_nodes_ptr (basic_block bb)
! {
! gcc_assert (!(bb->flags & BB_RTL));
! return &bb->il.tree->phi_nodes;
}
/* Set list of phi nodes of a basic block BB to L. */
*************** set_phi_nodes (basic_block bb, tree l)
*** 647,653 ****
{
tree phi;
! bb->phi_nodes = l;
for (phi = l; phi; phi = PHI_CHAIN (phi))
set_bb_for_stmt (phi, bb);
}
--- 659,666 ----
{
tree phi;
! gcc_assert (!(bb->flags & BB_RTL));
! bb->il.tree->phi_nodes = l;
for (phi = l; phi; phi = PHI_CHAIN (phi))
set_bb_for_stmt (phi, bb);
}
*************** phi_ssa_name_p (tree t)
*** 746,765 ****
/* ----------------------------------------------------------------------- */
/* Return a block_stmt_iterator that points to beginning of basic
block BB. */
static inline block_stmt_iterator
bsi_start (basic_block bb)
{
block_stmt_iterator bsi;
! if (bb->stmt_list)
! bsi.tsi = tsi_start (bb->stmt_list);
! else
{
- gcc_assert (bb->index < NUM_FIXED_BLOCKS);
bsi.tsi.ptr = NULL;
bsi.tsi.container = NULL;
}
bsi.bb = bb;
return bsi;
}
--- 759,795 ----
/* ----------------------------------------------------------------------- */
+ /* Returns the list of statements in BB. */
+
+ static inline tree
+ bb_stmt_list (basic_block bb)
+ {
+ gcc_assert (!(bb->flags & BB_RTL));
+ return bb->il.tree->stmt_list;
+ }
+
+ /* Sets the list of statements in BB to LIST. */
+
+ static inline void
+ set_bb_stmt_list (basic_block bb, tree list)
+ {
+ gcc_assert (!(bb->flags & BB_RTL));
+ bb->il.tree->stmt_list = list;
+ }
+
/* Return a block_stmt_iterator that points to beginning of basic
block BB. */
static inline block_stmt_iterator
bsi_start (basic_block bb)
{
block_stmt_iterator bsi;
! if (bb->index < NUM_FIXED_BLOCKS)
{
bsi.tsi.ptr = NULL;
bsi.tsi.container = NULL;
}
+ else
+ bsi.tsi = tsi_start (bb_stmt_list (bb));
bsi.bb = bb;
return bsi;
}
*************** static inline block_stmt_iterator
*** 784,797 ****
bsi_last (basic_block bb)
{
block_stmt_iterator bsi;
! if (bb->stmt_list)
! bsi.tsi = tsi_last (bb->stmt_list);
! else
{
- gcc_assert (bb->index < NUM_FIXED_BLOCKS);
bsi.tsi.ptr = NULL;
bsi.tsi.container = NULL;
}
bsi.bb = bb;
return bsi;
}
--- 814,827 ----
bsi_last (basic_block bb)
{
block_stmt_iterator bsi;
!
! if (bb->index < NUM_FIXED_BLOCKS)
{
bsi.tsi.ptr = NULL;
bsi.tsi.container = NULL;
}
+ else
+ bsi.tsi = tsi_last (bb_stmt_list (bb));
bsi.bb = bb;
return bsi;
}
Index: cfgexpand.c
===================================================================
*** cfgexpand.c (revision 124042)
--- cfgexpand.c (working copy)
*************** expand_gimple_tailcall (basic_block bb,
*** 1439,1445 ****
static basic_block
expand_gimple_basic_block (basic_block bb)
{
! block_stmt_iterator bsi = bsi_start (bb);
tree stmt = NULL;
rtx note, last;
edge e;
--- 1439,1446 ----
static basic_block
expand_gimple_basic_block (basic_block bb)
{
! tree_stmt_iterator tsi;
! tree stmts = bb_stmt_list (bb);
tree stmt = NULL;
rtx note, last;
edge e;
*************** expand_gimple_basic_block (basic_block b
*** 1452,1462 ****
bb->index);
}
init_rtl_bb_info (bb);
bb->flags |= BB_RTL;
! if (!bsi_end_p (bsi))
! stmt = bsi_stmt (bsi);
if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
{
--- 1453,1465 ----
bb->index);
}
+ bb->il.tree = NULL;
init_rtl_bb_info (bb);
bb->flags |= BB_RTL;
! tsi = tsi_start (stmts);
! if (!tsi_end_p (tsi))
! stmt = tsi_stmt (tsi);
if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
{
*************** expand_gimple_basic_block (basic_block b
*** 1469,1475 ****
BB_HEAD (bb) = NEXT_INSN (last);
if (NOTE_P (BB_HEAD (bb)))
BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
! bsi_next (&bsi);
note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
maybe_dump_rtl_for_tree_stmt (stmt, last);
--- 1472,1478 ----
BB_HEAD (bb) = NEXT_INSN (last);
if (NOTE_P (BB_HEAD (bb)))
BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
! tsi_next (&tsi);
note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
maybe_dump_rtl_for_tree_stmt (stmt, last);
*************** expand_gimple_basic_block (basic_block b
*** 1493,1501 ****
ei_next (&ei);
}
! for (; !bsi_end_p (bsi); bsi_next (&bsi))
{
! tree stmt = bsi_stmt (bsi);
basic_block new_bb;
if (!stmt)
--- 1496,1504 ----
ei_next (&ei);
}
! for (; !tsi_end_p (tsi); tsi_next (&tsi))
{
! tree stmt = tsi_stmt (tsi);
basic_block new_bb;
if (!stmt)
Index: basic-block.h
===================================================================
*** basic-block.h (revision 124042)
--- basic-block.h (working copy)
*************** struct rtl_bb_info;
*** 213,221 ****
/* Basic block information indexed by block number. */
struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
{
- /* Pointers to the first and last trees of the block. */
- tree stmt_list;
-
/* The edges into and out of the block. */
VEC(edge,gc) *preds;
VEC(edge,gc) *succs;
--- 213,218 ----
*************** struct basic_block_def GTY((chain_next (
*** 234,245 ****
struct basic_block_def *next_bb;
union basic_block_il_dependent {
struct rtl_bb_info * GTY ((tag ("1"))) rtl;
} GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
- /* Chain of PHI nodes for this block. */
- tree phi_nodes;
-
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
--- 231,243 ----
struct basic_block_def *next_bb;
union basic_block_il_dependent {
+ /* In gimple, we store the list of statements of the block here.
+ TREE_CHAIN of this field contains the list of phi nodes of
+ the block. */
+ struct tree_bb_info * GTY ((tag ("0"))) tree;
struct rtl_bb_info * GTY ((tag ("1"))) rtl;
} GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
*************** struct rtl_bb_info GTY(())
*** 277,282 ****
--- 275,289 ----
int visited;
};
+ struct tree_bb_info GTY(())
+ {
+ /* Pointers to the first and last trees of the block. */
+ tree stmt_list;
+
+ /* Chain of PHI nodes for this block. */
+ tree phi_nodes;
+ };
+
typedef struct basic_block_def *basic_block;
DEF_VEC_P(basic_block);
Index: tree-cfg.c
===================================================================
*** tree-cfg.c (revision 124042)
--- tree-cfg.c (working copy)
*************** create_bb (void *h, void *e, basic_block
*** 368,374 ****
bb->index = last_basic_block;
bb->flags = BB_NEW;
! bb->stmt_list = h ? (tree) h : alloc_stmt_list ();
/* Add the new block to the linked list of blocks. */
link_block (bb, after);
--- 368,375 ----
bb->index = last_basic_block;
bb->flags = BB_NEW;
! bb->il.tree = GGC_CNEW (struct tree_bb_info);
! set_bb_stmt_list (bb, h ? (tree) h : alloc_stmt_list ());
/* Add the new block to the linked list of blocks. */
link_block (bb, after);
*************** tree_merge_blocks (basic_block a, basic_
*** 1306,1314 ****
}
/* Merge the chains. */
! last = tsi_last (a->stmt_list);
! tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
! b->stmt_list = NULL;
}
--- 1307,1315 ----
}
/* Merge the chains. */
! last = tsi_last (bb_stmt_list (a));
! tsi_link_after (&last, bb_stmt_list (b), TSI_NEW_STMT);
! set_bb_stmt_list (b, NULL_TREE);
}
*************** remove_bb (basic_block bb)
*** 1944,2000 ****
}
/* Remove all the instructions in the block. */
! for (i = bsi_start (bb); !bsi_end_p (i);)
{
! tree stmt = bsi_stmt (i);
! if (TREE_CODE (stmt) == LABEL_EXPR
! && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
! || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
! {
! basic_block new_bb;
! block_stmt_iterator new_bsi;
!
! /* A non-reachable non-local label may still be referenced.
! But it no longer needs to carry the extra semantics of
! non-locality. */
! if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
{
! DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
! FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
}
! new_bb = bb->prev_bb;
! new_bsi = bsi_start (new_bb);
! bsi_remove (&i, false);
! bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
! }
! else
! {
! /* Release SSA definitions if we are in SSA. Note that we
! may be called when not in SSA. For example,
! final_cleanup calls this function via
! cleanup_tree_cfg. */
! if (gimple_in_ssa_p (cfun))
! release_defs (stmt);
!
! bsi_remove (&i, true);
! }
! /* Don't warn for removed gotos. Gotos are often removed due to
! jump threading, thus resulting in bogus warnings. Not great,
! since this way we lose warnings for gotos in the original
! program that are indeed unreachable. */
! if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
! {
#ifdef USE_MAPPED_LOCATION
! if (EXPR_HAS_LOCATION (stmt))
! loc = EXPR_LOCATION (stmt);
#else
! source_locus t;
! t = EXPR_LOCUS (stmt);
! if (t && LOCATION_LINE (*t) > 0)
! loc = t;
#endif
}
}
--- 1945,2004 ----
}
/* Remove all the instructions in the block. */
! if (bb_stmt_list (bb) != NULL_TREE)
{
! for (i = bsi_start (bb); !bsi_end_p (i);)
! {
! tree stmt = bsi_stmt (i);
! if (TREE_CODE (stmt) == LABEL_EXPR
! && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
! || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
{
! basic_block new_bb;
! block_stmt_iterator new_bsi;
!
! /* A non-reachable non-local label may still be referenced.
! But it no longer needs to carry the extra semantics of
! non-locality. */
! if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
! {
! DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
! FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
! }
!
! new_bb = bb->prev_bb;
! new_bsi = bsi_start (new_bb);
! bsi_remove (&i, false);
! bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
}
+ else
+ {
+ /* Release SSA definitions if we are in SSA. Note that we
+ may be called when not in SSA. For example,
+ final_cleanup calls this function via
+ cleanup_tree_cfg. */
+ if (gimple_in_ssa_p (cfun))
+ release_defs (stmt);
! bsi_remove (&i, true);
! }
! /* Don't warn for removed gotos. Gotos are often removed due to
! jump threading, thus resulting in bogus warnings. Not great,
! since this way we lose warnings for gotos in the original
! program that are indeed unreachable. */
! if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
! {
#ifdef USE_MAPPED_LOCATION
! if (EXPR_HAS_LOCATION (stmt))
! loc = EXPR_LOCATION (stmt);
#else
! source_locus t;
! t = EXPR_LOCUS (stmt);
! if (t && LOCATION_LINE (*t) > 0)
! loc = t;
#endif
+ }
}
}
*************** remove_bb (basic_block bb)
*** 2011,2016 ****
--- 2015,2021 ----
#endif
remove_phi_nodes_and_edges_for_unreachable_block (bb);
+ bb->il.tree = NULL;
}
*************** tree_verify_flow_info (void)
*** 3651,3665 ****
edge e;
edge_iterator ei;
! if (ENTRY_BLOCK_PTR->stmt_list)
{
! error ("ENTRY_BLOCK has a statement list associated with it");
err = 1;
}
! if (EXIT_BLOCK_PTR->stmt_list)
{
! error ("EXIT_BLOCK has a statement list associated with it");
err = 1;
}
--- 3656,3670 ----
edge e;
edge_iterator ei;
! if (ENTRY_BLOCK_PTR->il.tree)
{
! error ("ENTRY_BLOCK has IL associated with it");
err = 1;
}
! if (EXIT_BLOCK_PTR->il.tree)
{
! error ("EXIT_BLOCK has IL associated with it");
err = 1;
}
*************** tree_split_block (basic_block bb, void *
*** 4200,4206 ****
{
block_stmt_iterator bsi;
tree_stmt_iterator tsi_tgt;
! tree act;
basic_block new_bb;
edge e;
edge_iterator ei;
--- 4205,4211 ----
{
block_stmt_iterator bsi;
tree_stmt_iterator tsi_tgt;
! tree act, list;
basic_block new_bb;
edge e;
edge_iterator ei;
*************** tree_split_block (basic_block bb, void *
*** 4240,4247 ****
brings ugly quadratic memory consumption in the inliner.
(We are still quadratic since we need to update stmt BB pointers,
sadly.) */
! new_bb->stmt_list = tsi_split_statement_list_before (&bsi.tsi);
! for (tsi_tgt = tsi_start (new_bb->stmt_list);
!tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
--- 4245,4253 ----
brings ugly quadratic memory consumption in the inliner.
(We are still quadratic since we need to update stmt BB pointers,
sadly.) */
! list = tsi_split_statement_list_before (&bsi.tsi);
! set_bb_stmt_list (new_bb, list);
! for (tsi_tgt = tsi_start (list);
!tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);