[PATCH GCC]Improve candidate selecting in IVOPT

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

Hi,
As analyzed in PR62178, IVOPT can't find the optimal iv set for that case.
The problem with current heuristic algorithm is it only replaces candidate
with ones not in current solution one by one, starting from small solution.
This patch adds another heuristic which starts from assigning the best
candidate for each iv use, then replaces candidate with ones in the current
solution.
Before this patch, there are two runs of find_optimal_set_1 to find the
optimal iv sets, we name them as set_a and set_b.  After this patch we will
have set_c.  At last, IVOPT chooses the best one from set_a/set_b/set_c.  To
prove that this patch is necessary, I collected instrumental data for gcc
bootstrap, spec2k, eembc and can confirm for some cases only the newly added
heuristic can find the optimal iv set.  The number of these cases in which
set_c is the optimal one is on the same level of set_b.
As for the compilation time, the newly added function actually is one
iteration of previous selection algorithm, it should be much faster than
previous process.

I also added one target dependent test case.
Bootstrap and test on x86_64, test on aarch64.  Any comments?

2014-09-30  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/62178
	* tree-ssa-loop-ivopts.c (enum sel_type): New.
	(iv_ca_add_use): Add parameter RELATED_P and find the best cand
	for iv use if it's true.
	(try_add_cand_for, get_initial_solution): Change paramter ORIGINALP
	to SELECT_TYPE and handle it.
	(find_optimal_iv_set_1): Ditto.
	(try_prune_iv_set, find_optimal_iv_set_2): New functions.
	(find_optimal_iv_set): Call find_optimal_iv_set_2 and choose the
	best candidate set.

gcc/testsuite/ChangeLog
2014-09-30  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/62178
	* gcc.target/aarch64/pr62178.c: New test.

Attachment: pr62178-20140910.txt
Description: Text document