IVOPT performance tuning patch.

IVOPT performance tuning patch. The main problem is a variant of maximal weight 
bipartite matching/assignment problem -- i.e., there is an additional global
cost function. The complexity of the algorighm to find the optimial solution
> O(n^2). The existing algorithm in gcc tries to find the solution in 3 stages:
1) Find the initial solution set (dynamic programing style)
2) Extend the solution set
3) Prune the soultion set.

The problem is that in step 1, the initial set tends to be too large so that
the final solution is very likely local optimal.

This patch addresses the problem and sees very large SPEC improvements.

Another area of problem is that ivopts often creates loop invariant expressions, and
such expressions increase register pressure which is not counted. This is addressed
in this patch.

The third main problem is the profile data is not considered in cost computation

The forth problem is that loop invariant comptuation's cost is not properly adjusted.



There are more tuning opportuties, namely:

1) Do not check ivs dependency during ivs set pruning (this improves deallII 8% on core2)
2) Unconditionally consider all important candidates in partial set expansion (in addition
to the extended solutino based on selected candidates)
3) revisit the two stage initial set computation.

From-SVN: r162653

1 files changed, 1 insertions, 1 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c
index 7c4236b..202ad1f 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c
@@ -8,5 +8,5 @@ void main (void)
     f2 ();
 }
 
-/* { dg-final { scan-tree-dump-times "!= 0" 4 "ivopts" } }  */
+/* { dg-final { scan-tree-dump-times "!= 0" 5 "ivopts" } }  */
 /* { dg-final { cleanup-tree-dump "ivopts" } }  */