[PATCH GCC]Improve IVOPT to handle outside and inside loop iv uses differently in GCC

["bin.cheng" <bin dot cheng at arm dot com>]

Hi,
GCC IVOPT has a problem that it doesn't differentiate between iv uses
outside of loop from inside ones.  It computes cost for outside iv use just
like inside ones, which is wrong because outside iv use should be computed
along loop exit edge and the cost should be amortized against loop iteration
number.  Lastly, the computation of outside iv use is inserted in loop,
rather along loop exit edge.

This is interesting since usually outside iv use should be handled
differently, or it hurts optimization in several ways like:
1) Wrong iv candidate is chosen because of inaccurate cost.
2) Extra computation in loop itself is redundant.
3) Extra code computing outside iv use in loop may increases register
pressure because both iv variables before and after stepping could be alive
at same time.
4) IVOPT generates code that it expects to stay as is, passes like DOM tends
to break this because of the extra computation.  This hurts targets with
auto-increment support more.

This patch fixes the problem.  Bootstrap and test on x86/x86_64/arm.
Richard, Zdenek,  does this look reasonable?

Thanks,
bin


gcc/testsuite/ChangeLog
2013-11-06  Bin Cheng  <bin.cheng@arm.com>

	* gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test.

2013-11-06  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-loop-ivopts.c (iv_use_p, iv_cand_p): Move around.
	(iv_use_location): New.
	(struct iv): Remove have_use_for and use_id.  New fields
	inside_use, outside_uses_vec and use_loc.
	(struct iv_use): New fields exit_edge and outside_use_p.
	(struct edge_info, edge_info_p): New.
	(struct ivopts_data): New fields alloc_uses_vecs, changed_bbs,
	edge_map and edge_obstack.
	(init_edge_info, get_edge_info): New.
	(dump_use): Dump outside/inside information for iv use.
	(tree_ssa_iv_optimize_init): Init new fields.
	(alloc_iv): Init new fields.  Remove have_use_for and use_id.
	(record_use): New parameter.  Record information for outside loop
	iv use.
	(find_interesting_uses_op): New parameter.  Handle inside and
	outside loop iv uses.
	(find_interesting_uses_cond, idx_record_use): Pass new argument.
	(find_interesting_uses_address): Likewise.
	(find_interesting_uses_stmt, create_new_iv): likewise.
	(find_interesting_uses_outside): Rename exit to exit_edge.
	New parameter normal_edge_p.  Pass new argument.
	(find_interesting_uses): Find iv uses in two passes.
	(get_computation): Compute cost at right position for iv use.
	(determine_use_iv_cost_generic): Ajust cost for outside loop iv use.
	(rewrite_use_outside_of_loop): New.
	(rewrite_use): Call rewrite_use_outside_of_loop.
	(remove_unused_ivs): Keep computation only for inner iv use.
	(free_loop_data):  Reset outside_uses_vec in various iv structures.
	Free alloc_uses_vecs and edge_map.
	(tree_ssa_iv_optimize_finalize): Free and reset.
	(tree_ssa_iv_optimize_loop): Create edge_map.
	(tree_ssa_iv_optimize): Call rewrite_into_loop_closed_ssa if
	necessary.

Attachment: ivopt-outside-use-20131102.txt
Description: Text document