OSDN Git Service

2004-09-08 Daniel Berlin <dberlin@dberlin.org>
[pf3gnuchains/gcc-fork.git] / gcc / tree-loop-linear.c
1 /* Linear Loop transforms
2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dberlin@dberlin.org>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "errors.h"
28 #include "ggc.h"
29 #include "tree.h"
30 #include "target.h"
31
32 #include "rtl.h"
33 #include "basic-block.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "timevar.h"
38 #include "cfgloop.h"
39 #include "expr.h"
40 #include "optabs.h"
41 #include "tree-chrec.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "tree-pass.h"
45 #include "varray.h"
46 #include "lambda.h"
47
48 /* Linear loop transforms include any composition of interchange,
49    scaling, skewing, and reversal.  They are used to change the
50    iteration order of loop nests in order to optimize data locality of
51    traversals, or remove dependences that prevent
52    parallelization/vectorization/etc.  
53
54    TODO: Determine reuse vectors/matrix and use it to determine optimal
55    transform matrix for locality purposes.
56    TODO: Completion of partial transforms.  */
57
58 /* Gather statistics for loop interchange.  Initializes SUM the sum of
59    all the data dependence distances carried by loop LOOP_NUMBER.
60    NB_DEPS_NOT_CARRIED_BY_LOOP is initialized to the number of
61    dependence relations for which the loop LOOP_NUMBER is not carrying
62    any dependence.  */
63
64 static void
65 gather_interchange_stats (varray_type dependence_relations, 
66                           unsigned int loop_number, 
67                           unsigned int *sum, 
68                           unsigned int *nb_deps_not_carried_by_loop)
69 {
70   unsigned int i;
71
72   *sum = 0;
73   *nb_deps_not_carried_by_loop = 0;
74   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
75     {
76       int dist;
77       struct data_dependence_relation *ddr = 
78         (struct data_dependence_relation *) 
79         VARRAY_GENERIC_PTR (dependence_relations, i);
80
81       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
82         {
83           /* Some constants will need tweaking, but not something that should
84              be user-accessible.  Thus, no --param.  */
85           *sum += 100;
86           continue;
87         }
88
89       /* When we know that there is no dependence, we know that there
90          is no reuse of the data.  */
91       if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
92         {
93           /* Ditto on the no --param here */
94           *sum += 1000;
95           continue;
96         }
97
98       dist = DDR_DIST_VECT (ddr)[loop_number];
99       if (dist == 0)
100         *nb_deps_not_carried_by_loop++;
101       else if (dist < 0)
102         *sum += -dist;
103       else
104         *sum += dist;
105     }
106 }
107
108 /* Apply to TRANS any loop interchange that minimize inner loop steps.
109    DEPTH is the depth of the loop nest, and DEPENDENCE_RELATIONS is an array
110    of dependence relations.
111    Returns the new transform matrix.  The smaller the reuse vector
112    distances in the inner loops, the fewer the cache misses.  */
113
114 static lambda_trans_matrix
115 try_interchange_loops (lambda_trans_matrix trans, 
116                        unsigned int depth,                     
117                        varray_type dependence_relations)
118 {
119   unsigned int loop_i, loop_j;
120   unsigned int steps_i, steps_j;
121   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
122   struct data_dependence_relation *ddr;
123
124   /* When there is an unknown relation in the dependence_relations, we
125      know that it is no worth looking at this loop nest: give up.  */
126   ddr = (struct data_dependence_relation *) 
127     VARRAY_GENERIC_PTR (dependence_relations, 0);
128   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
129     return trans;
130   
131   /* LOOP_I is always the outer loop.  */
132   for (loop_j = 1; loop_j < depth; loop_j++)
133     for (loop_i = 0; loop_i < loop_j; loop_i++)
134       {
135         gather_interchange_stats (dependence_relations, loop_i, &steps_i, 
136                                   &nb_deps_not_carried_by_i);
137         gather_interchange_stats (dependence_relations, loop_j, &steps_j, 
138                                   &nb_deps_not_carried_by_j);
139         
140         /* Heuristics for loop interchange profitability:
141            1. Inner loops should have smallest steps.
142            2. Inner loops should contain more dependence relations not
143            carried by the loop.
144         */
145         if (steps_i < steps_j 
146             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j)
147           {
148             lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
149         
150             /* Validate the resulting matrix.  When the transformation
151                is not valid, reverse to the previous matrix.  
152                
153                FIXME: In this case of transformation it could be
154                faster to verify the validity of the interchange
155                without applying the transform to the matrix.  But for
156                the moment do it cleanly: this is just a prototype.  */
157             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
158               lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
159           }
160       }
161   
162   return trans;
163 }
164
165 /* Perform a set of linear transforms on LOOPS.  */
166
167 void
168 linear_transform_loops (struct loops *loops)
169 {
170   unsigned int i;
171
172   for (i = 1; i < loops->num; i++)
173     {
174       unsigned int depth = 0;
175       varray_type datarefs;
176       varray_type dependence_relations;
177       struct loop *loop_nest = loops->parray[i];
178       struct loop *temp;
179       VEC (tree) *oldivs;
180       VEC (tree) *invariants;
181       lambda_loopnest before, after;
182       lambda_trans_matrix trans;
183       bool problem = false;
184       /* If it's not a loop nest, we don't want it.
185          We also don't handle sibling loops properly, 
186          which are loops of the following form:
187          for (i = 0; i < 50; i++)
188            {
189              for (j = 0; j < 50; j++)
190                {
191                 ...
192                }
193            for (j = 0; j < 50; j++)
194                {
195                 ...
196                }
197            } */
198       if (!loop_nest->inner)
199         continue;
200       for (temp = loop_nest; temp; temp = temp->inner)
201         {
202           flow_loop_scan (temp, LOOP_ALL);
203           /* If we have a sibling loop or multiple exit edges, jump ship.  */
204           if (temp->next || temp->num_exits != 1)
205             {
206               problem = true;
207               break;
208             }
209           depth ++;
210         }
211       if (problem)
212         continue;
213
214       /* Analyze data references and dependence relations using scev.  */      
215  
216       VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
217       VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
218                                "dependence_relations");
219       
220   
221       compute_data_dependences_for_loop (depth, loop_nest,
222                                          &datarefs, &dependence_relations);
223       if (dump_file && (dump_flags & TDF_DETAILS))
224         {
225           unsigned int j;
226           for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
227             {
228               struct data_dependence_relation *ddr = 
229                 (struct data_dependence_relation *) 
230                 VARRAY_GENERIC_PTR (dependence_relations, j);
231
232               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
233                 {
234                   fprintf (dump_file, "DISTANCE_V (");
235                   print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), 
236                                        loops->num);
237                   fprintf (dump_file, ")\n");
238                   fprintf (dump_file, "DIRECTION_V (");
239                   print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), 
240                                        loops->num);
241                   fprintf (dump_file, ")\n");
242                 }
243             }
244           fprintf (dump_file, "\n\n");
245         }
246       /* Build the transformation matrix.  */
247       trans = lambda_trans_matrix_new (depth, depth);
248       lambda_matrix_id (LTM_MATRIX (trans), depth);
249       trans = try_interchange_loops (trans, depth, dependence_relations);
250
251       /* Check whether the transformation is legal.  */
252       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
253         {
254           if (dump_file)
255             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
256           continue;
257         }
258       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs, 
259                                                 &invariants);
260       if (!before)
261         continue;
262             
263       if (dump_file)
264         {
265           fprintf (dump_file, "Before:\n");
266           print_lambda_loopnest (dump_file, before, 'i');
267         }
268   
269       after = lambda_loopnest_transform (before, trans);
270       if (dump_file)
271         {
272           fprintf (dump_file, "After:\n");
273           print_lambda_loopnest (dump_file, after, 'u');
274         }
275       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
276                                        after, trans);
277       oldivs = NULL;
278       invariants = NULL;
279       free_dependence_relations (dependence_relations);
280       free_data_refs (datarefs);
281     }
282 }