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]

[PATCH GCC][3/4]Generalize dead store elimination (or store motion) across loop iterations in predcom

For the moment, tree-predcom.c only supports invariant/load-loads/store-loads chains.
This patch generalizes dead store elimination (or store motion) across loop iterations in
predictive commoning pass by supporting store-store chain.  As comment in the patch:

   Apart from predictive commoning on Load-Load and Store-Load chains, we
   also support Store-Store chains -- stores killed by other store can be
   eliminated.  Given below example:

     for (i = 0; i < n; i++)
	 a[i] = 1;
	 a[i+2] = 2;

   It can be replaced with:

     t0 = a[0];
     t1 = a[1];
     for (i = 0; i < n; i++)
	 a[i] = 1;
	 t2 = 2;
	 t0 = t1;
	 t1 = t2;
     a[n] = t0;
     a[n+1] = t1;

   If the loop runs more than 1 iterations, it can be further simplified into:

     for (i = 0; i < n; i++)
	 a[i] = 1;
     a[n] = 2;
     a[n+1] = 2;

   The interesting part is this can be viewed either as general store motion
   or general dead store elimination in either intra/inter-iterations way.

There are number of interesting facts about this enhancement:
a) This patch supports dead store elimination for both across-iteration case and single-iteration
     case.  For the latter, it is dead store elimination.
b) There are advantages supporting dead store elimination in predcom, for example, it has
     complete information about memory address.  On the contrary, DSE pass can only handle
     memory references with exact the same memory address expression.
c) It's cheap to support store-stores chain in predcom based on existing code.
d) As commented, the enhancement can be viewed as either generalized dead store elimination
     or generalized store motion.  I prefer DSE here.

Bootstrap(O2/O3) in patch series on x86_64 and AArch64.  Is it OK?

2017-06-21  Bin Cheng  <>

	* tree-predcom.c: Revise general description of pass.
	(enum chain_type): New enum type for store elimination.
	(struct chain): New field supporting store elimination.
	(dump_chain): Dump store-stores chain.
	(release_chain): Release resources.
	(split_data_refs_to_components): Compute and create component
	contains only stores for elimination.
	(get_chain_last_ref_at): New function.
	(make_invariant_chain): Initialization.
	(make_rooted_chain): Specify chain type in parameter.
	(add_looparound_copies): Skip for store-stores chain.
	(determine_roots_comp): Compute type of chain and pass it to
	(initialize_root_vars_store_elim_2): New function.
	(finalize_eliminated_stores): New function.
	(remove_stmt): Handle store for elimination.
	(execute_pred_commoning_chain): Execute predictive commoning on
	store-store chains.
	(determine_unroll_factor): Skip unroll for store-stores chain.
	(prepare_initializers_chain_store_elim): New function.
	(prepare_initializers_chain): Hanlde store-store chain.
	(prepare_finalizers_chain, prepare_finalizers): New function.
	(tree_predictive_commoning_loop): Return integer value indicating
	if loop is unrolled or lcssa form is corrupted.
	(tree_predictive_commoning): Rewrite for lcssa form if necessary.

2017-06-21  Bin Cheng  <>

	* gcc.dg/tree-ssa/predcom-dse-1.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-2.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-3.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-4.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-5.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-6.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-7.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-8.c: New test.
	* gcc.dg/tree-ssa/predcom-dse-9.c: New test.

Attachment: predcom-generalize-dse-20170622.txt
Description: predcom-generalize-dse-20170622.txt

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