This is the mail archive of the 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]

[mem-ssa]: WIP. Factoring memory PHIs.

This patch breaks the branch, but I need to iterate over the design
because it is not going in the direction I need it to go.  The concept
of memory PHI factoring addresses the problem that we currently create
PHI nodes for every memory symbol, causing an unnecessary number of PHI

This duplication of PHI nodes is detrimental because it essentially
undoes all the factoring done in the memory stores:

For instance,

p_3 points-to {a, b, c, d, e}

# .MEM_3 = VDEF <a_10, .MEM_5, d_8>
*p_3 = ...

if (...)
  # a_11 = VDEF <.MEM_3>
  a = ...
a_12 = PHI <.MEM_3, a_11>
b_13 = PHI <.MEM_3, .MEM_3>
c_14 = PHI <.MEM_3, .MEM_3>
d_15 = PHI <.MEM_3, .MEM_3>
e_16 = PHI <.MEM_3, .MEM_3>

# VUSE <a_12, b_13, c_14, d_15, e_16>
x_9 = *p_3

All the factoring we did for {b, c, d, e} is undone by all those
unnecessary PHI nodes (b_13, c_14, d_15 and e_16).  Not only that, we
waste quite a bit of time computing PHI placement for all these symbols,
which typically end up in the exact same block.

So, the PHI factoring algorithm I've been working on does the following:

# .MEM_3 = VDEF <a_10, .MEM_5, d_8>
*p_3 = ...

if (...)
  # a_11 = VDEF <.MEM_3>
  a = ...
a_12 = PHI <.MEM_3, a_11>
.MEM_13 = PHI <.MEM_3, .MEM_0(D)>

# VUSE <a_12, .MEM_13>
x_9 = *p_3

None of the symbols in the set {b, c, d, e} have definitions inside the
if(), so they get the default definiton for .MEM (.MEM_0).

I have yet not found an elegant solution to the creation of factored PHI
nodes.  This patch addresses a few other things as well, like the
interface to get the sets of loads and stores from a statement, which
should not change a lot (though Andrew will likely want to change the
way we update these sets).

I will likely need several changes to the factoring/unfactoring code.
It's both slow and buggy.  I am still not convinced all this factoring
buys us much in the end, but I cannot tell for sure until I can
bootstrap and compare against mainline.  The factoring logic needs to do
tons of bitmap operations, which in the end may end up being as
expensive as what we do today.  We'll see.

So, bootstraps are broken on mem-ssa.  The C testsuite works, and the
other languages may work to some extent.

	NOTE: WIP.  With these changes, the branch does not bootstrap.

	* tree-ssa-operands.h (dump_loads_and_stores,
	debug_loads_and_stores, dump_decl_set, debug_decl_set):
	(struct mem_syms_map_d): Declare.
	(mem_syms_map_t): Declare.
	(add_loads_and_stores, move_loads_and_stores,
	delete_loads_and_stores): Declare.
	* tree-into-ssa.c (struct ssa_name_info): Add field
	(syms_stored_in_bb): New local variable.
	(syms_with_phi_in_bb): New local variable.
	(syms_to_factor_in_bb): New local variable.
	(struct unfactored_phis_d): Declare.
	(unfactored_phis_t): Declare.
	(first_unfactored_phi): New local variable.
	(last_unfactored_phi): New local variable.
	(unfactored_phis): New local variable.
	(last_dom_num): New local variable.
	(mem_syms_tbl): Remove.
	(dump_stored_syms): New.
	(debug_stored_syms): New.
	(dump_unfactored_phis): New.
	(debug_unfactored_phis): New.
	(dump_unfactored_phi): New.
	(debug_unfactored_phi): New.
	(get_dom_num): New.
	(get_name_dom_num): New.
	(set_next_dom_num): New.
	(unfactored_phis_hash): New.
	(unfactored_phis_eq): New.
	(unfactored_phis): New.
	(mem_syms_hash): Remove.
	(mem_syms_eq): Remove.
	(mem_syms_free): Remove.
	(add_syms_with_phi): New.
	(add_stored_syms): New.
	(add_stored_sym): New.
	(mark_def_sites): Do not process statements that reference
	(compute_idf): Rename from find_idf.
	When inserting PHI nodes for .MEM, determine set of symbols to
	associate initially using SYMS_STORED_IN_BB and
	(insert_phi_nodes_for): Call create_factored_phi_node if
	(insert_phi_nodes): Likewise.
	(rewrite_memory_stmt): Remove.
	(rewrite_update_init_block): Call set_next_dom_num.
	PHI nodes for .MEM become the current definition for every
	symbol factored in them.
	(preserve_needed_names_in_vops): Remove.
	(rewrite_vops): New.
	(rewrite_update_stmt_vops): Call it.
	(rewrite_update_stmt): Call set_next_dom_num.
	(add_reached_sym): New.
	(lookup_unfactored_phi): New.
	(get_unfactored_phi): New.
	(split_factored_phi): New.
	(replace_factored_phi_argument): New.
	(rewrite_update_phi_arguments): Call it.
	(init_ssa_renamer): Initialize last_dom_num,
	syms_stored_in_bb, syms_with_phi_in_bb, syms_to_factor_in_bb.
	(fini_ssa_renamer): Deallocate syms_stored_in_bb,
	syms_with_phi_in_bb, syms_to_factor_in_bb.
	(prepare_block_for_update): Fill-in syms_with_phi_in_bb and
	(delete_update_ssa): Deallocate unfactored_phis and
	(add_to_fixup_queues): New.
	(compute_currdefs_for): New.
	(fixup_unfactored_phis): New.
	(update_ssa): Insert PHI nodes for .MEM separately.
	Do not try to insert PHI nodes for memory symbols.
	Call fixup_unfactored_phis.
	* tree-dump.c (dump_options): Add entry for "memsyms".
	* tree-pretty-print.c (debug_generic_expr): Add flag
	(debug_tree_chain): Likewise.
	(dump_symbols): New.
	(dump_generic_node): Call it if TDF_MEMSYMS is given.
	(dump_vops): Likewise.
	* tree-ssa-loop-manip.c (split_loop_exit_edge): Ignore memory
	* tree-pass.h (TDF_MEMSYMS): Define.
	* bitmap.c (bitmap_singleton_p): New.
	* bitmap.h (bitmap_singleton_p): Declare.
	* tree-phinodes.c (release_phi_node): Call
	(resize_phi_node): Call move_loads_and_stores.
	(create_phi_node_1): New.
	(create_phi_node): Call it.
	(create_factored_phi_node): New.
	(remove_phi_node): Add new boolean argument RELEASE_LHS_P.  If
	it is true, call release_ssa_name.
	Update all callers.
	* tree-ssa-alias.c (init_alias_info): The first time aliases
	are computed mark every memory symbol to be renamed.
	* timevar.def (TV_TREE_SSA_PHI_UNFACTOR): New.
	* tree-vectorizer.c (slpeel_update_phi_nodes_for_guard1): Only
	handle LCSSA PHIs for GIMPLE registers.
	* tree-vectorizer.h (vect_memsyms_to_rename): Rename from
	vect_vnames_to_rename.  Update all users.
	* tree-flow-inline.h (zero_imm_uses_p): New.
	* tree-ssa.c (verify_ssa_name): Do not verify sub-variables
	for memory symbols.
	Verify that every memory name uses the canonical MEM_0
	(verify_use): Add argument SYMS_IN_FACTORED_PHIS.  Update all
	Add verification for PHI nodes that reference memory.
	(stmt_references_memory_p): Move to tree-ssa-operands.c
	(walk_use_def_chains_1): Guard against NULL PHI arguments.
	* tree-ssa-loop-prefetch.c (SSA_NAME_VAR): Remove.
	* tree-flow.h (struct stmt_ann_d): Add bitfield
	(create_factored_phi_node): Declare.
	* tree-cfg.c
	(bsi_remove): Call delete_loads_and_stores if needed.
	(bsi_replace): Likewise.
	(tree_make_forwarder_block): Call create_factored_phi_node if
	(tree_duplicate_bb): Likewise.
	* tree-ssanames.c (release_defs): Remove assertion against
	* tree-ssa-operands.c (mem_syms_tbl): New local variable.
	(mem_syms_hash): New.
	(mem_syms_eq): New.
	(mem_syms_free): New.
	(init_ssa_operands): Intialize mem_syms_tbl.
	(fini_ssa_operands): Delete mem_syms_tbl.
	(add_virtual_operator): Do nothing if aliases_computed_p is
	(add_mem_symbol): Do nothing if stored_syms is not set.
	(get_mem_symbols_in_indirect_ref): Process statement even if
	aliases have not been computed.
	(add_stmt_operand): Mark statement as referencing memory if
	(get_indirect_ref_operands): Likewise.
	(get_tmr_operands): Likewise.
	(get_call_expr_operands): Likewise.
	(get_asm_expr_operands): Likewise.
	(build_ssa_operands): Initialize references_memory annotation
	to false.
	If has_volatile_ops has been marked by the parser, also set
	(get_loads_and_stores): Change interface to return sets of
	loads and stores in a structure.  Update all callers.
	(delete_loads_and_stores): New.
	(add_loads_and_stores): New.
	(move_loads_and_stores): New.
	(update_loads_and_stores): New.
	(update_stmt_operands): Call update_loads_and_stores if
	(mark_difference_for_renaming): Compute difference without
	clobbering the input sets.
	(stmt_references_memory_p): Move from tree-ssa.c.  Check the
	statement annotation.

Attachment: 20061011-phi-unfactoring.diff.gz
Description: GNU Zip compressed data

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