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

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

Ping and CC Zdenek with the right email.

Thanks,
bin

> -----Original Message-----
> From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-
> owner@gcc.gnu.org] On Behalf Of bin.cheng
> Sent: Wednesday, November 06, 2013 5:51 PM
> To: gcc-patches@gcc.gnu.org
> Cc: Richard Biener; ook@ucw.cz
> Subject: [PATCH GCC]Improve IVOPT to handle outside and inside loop iv
> uses differently in GCC
> 
> 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.