ivopt_mult_3.c
514 Bytes
-
IVOPT performance tuning patch. · 18081149
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
Xinliang David Li committed