[PATCH GCC][PR62173 partial/2]Improve overflow check on SCEV in IVOPTs using vrp info

["Bin Cheng" <bin dot cheng at arm dot com>]

Hi,
For the specific case reported in PR62173, overflow check on SCEV can be
improved using range information.  Precisely, it's range information of ssa
name in IV's base that helps, rather than range information of the IV
itself.  Since the IV is computed in the form of "IV_var = <var_base,
IV_var_offset>" in loop header, we can derive that var_base takes IV_var's
range information in the loop.  Even though this may not hold in other parts
of program.  To address this, this patch iterates each phi node in loop's
header and propagates range information from IV to base var.  Of course, the
range information should be restored after IVOPTs.  For now, we only
propagate IV's range information to base var if it hasn't had it.  This can
be extended to refine the existing range information.
Moreover, because of loop header copying, it's very likely to have entry
condition for the loop.  we also use this to further improve the range
information.  The patch does this by iterating upwards in dominator tree.
Actually the range information wouldn't be enough in this exact case.  

I was told this causes small regression in some benchmark.  But I did saw
inner-most loops are improved obviously with this and the hotspot of that
benchmark isn't affected at all.  I will further go through all the code
changes later.  Also there are couple of possible improvement, for example,
factor out the macro; don't iterate dominating tree repeatedly for each phi
node.

It passes bootstrap and regtest on both x86_64 and aarch64.  But I would
like to hear more comments on the idea itself then do some refinement.
So any comments?

Thanks,
bin

2015-02-13  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/62173
	* tree-ssa-loop-niter.h (split_to_var_and_offset): Expose it.
	(refine_bounds_using_guard): Expose it.  Change parameters by
	using below, up directly.
	* tree-ssa-loop-niter.c (split_to_var_and_offset): Expose it.
	(refine_bounds_using_guard): Expose it.  Change parameters by
	using below, up directly.
	(bound_difference): Change arguments.
	(scev_probably_wraps_p): Use range info when checking wrap behavior.
	* tree-ssa-loop-ivopts.c (name_range_info_map): New field in struct
	ivopts_data.
	(tree_ssa_iv_optimize_init): Initialize name_range_info_map.
	(tree_ssa_iv_optimize_finalize): Release name_range_info_map.
	(MAX_DOMINATORS_TO_WALK): New macro.
	(refine_ssa_name_range_info, refine_range_info_for_loop)
	(restore_range_info_for_loop): New functions.
	(tree_ssa_iv_optimize): Refine and restore range info for loop.

gcc/testsuite/ChangeLog
2015-02-13  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/62173
	* gcc.dg/tree-ssa/pr62173.c: New test.

Attachment: pr62173-20150203.txt
Description: Text document