OSDN Git Service

* tree-vrp.c (adjust_range_with_scev): Use get_chrec_loop.
[pf3gnuchains/gcc-fork.git] / gcc / tree-loop-linear.c
1 /* Linear Loop transforms
2    Copyright (C) 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "target.h"
30
31 #include "rtl.h"
32 #include "basic-block.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "tree-dump.h"
36 #include "timevar.h"
37 #include "cfgloop.h"
38 #include "expr.h"
39 #include "optabs.h"
40 #include "tree-chrec.h"
41 #include "tree-data-ref.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-pass.h"
44 #include "lambda.h"
45
46 /* Linear loop transforms include any composition of interchange,
47    scaling, skewing, and reversal.  They are used to change the
48    iteration order of loop nests in order to optimize data locality of
49    traversals, or remove dependences that prevent
50    parallelization/vectorization/etc.  
51
52    TODO: Determine reuse vectors/matrix and use it to determine optimal
53    transform matrix for locality purposes.
54    TODO: Completion of partial transforms.  */
55
56 /* Gather statistics for loop interchange.  LOOP is the loop being
57    considered. The first loop in the considered loop nest is
58    FIRST_LOOP, and consequently, the index of the considered loop is
59    obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
60    
61    Initializes:
62    - DEPENDENCE_STEPS the sum of all the data dependence distances
63    carried by loop LOOP,
64
65    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
66    for which the loop LOOP is not carrying any dependence,
67
68    - ACCESS_STRIDES the sum of all the strides in LOOP.
69
70    Example: for the following loop,
71
72    | loop_1 runs 1335 times
73    |   loop_2 runs 1335 times
74    |     A[{{0, +, 1}_1, +, 1335}_2]
75    |     B[{{0, +, 1}_1, +, 1335}_2]
76    |   endloop_2
77    |   A[{0, +, 1336}_1]
78    | endloop_1
79
80    gather_interchange_stats (in loop_1) will return 
81    DEPENDENCE_STEPS = 3002
82    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
83    ACCESS_STRIDES = 10694
84
85    gather_interchange_stats (in loop_2) will return 
86    DEPENDENCE_STEPS = 3000
87    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
88    ACCESS_STRIDES = 8010
89 */
90
91 static void
92 gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations,
93                           VEC (data_reference_p, heap) *datarefs,
94                           struct loop *loop,
95                           struct loop *first_loop,
96                           unsigned int *dependence_steps, 
97                           unsigned int *nb_deps_not_carried_by_loop, 
98                           unsigned int *access_strides)
99 {
100   unsigned int i, j;
101   struct data_dependence_relation *ddr;
102   struct data_reference *dr;
103
104   *dependence_steps = 0;
105   *nb_deps_not_carried_by_loop = 0;
106   *access_strides = 0;
107
108   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
109     {
110       /* If we don't know anything about this dependence, or the distance
111          vector is NULL, or there is no dependence, then there is no reuse of
112          data.  */
113       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
114           || DDR_ARE_DEPENDENT (ddr) == chrec_known
115           || DDR_NUM_DIST_VECTS (ddr) == 0)
116         continue;
117
118       for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
119         {
120           int dist = DDR_DIST_VECT (ddr, j)[loop->depth - first_loop->depth];
121
122           if (dist == 0)
123             (*nb_deps_not_carried_by_loop) += 1;
124
125           else if (dist < 0)
126             (*dependence_steps) += -dist;
127
128           else
129             (*dependence_steps) += dist;
130         }
131     }
132
133   /* Compute the access strides.  */
134   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
135     {
136       unsigned int it;
137       tree stmt = DR_STMT (dr);
138       struct loop *stmt_loop = loop_containing_stmt (stmt);
139       struct loop *inner_loop = first_loop->inner;
140       
141       if (inner_loop != stmt_loop 
142           && !flow_loop_nested_p (inner_loop, stmt_loop))
143         continue;
144       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
145         {
146           tree chrec = DR_ACCESS_FN (dr, it);
147           tree tstride = evolution_part_in_loop_num 
148             (chrec, loop->num);
149           
150           if (tstride == NULL_TREE
151               || TREE_CODE (tstride) != INTEGER_CST)
152             continue;
153           
154           (*access_strides) += int_cst_value (tstride);
155         }
156     }
157 }
158
159 /* Attempt to apply interchange transformations to TRANS to maximize the
160    spatial and temporal locality of the loop.  
161    Returns the new transform matrix.  The smaller the reuse vector
162    distances in the inner loops, the fewer the cache misses.
163    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
164    nest.  */
165
166
167 static lambda_trans_matrix
168 try_interchange_loops (lambda_trans_matrix trans, 
169                        unsigned int depth,                     
170                        VEC (ddr_p, heap) *dependence_relations,
171                        VEC (data_reference_p, heap) *datarefs,
172                        struct loop *first_loop)
173 {
174   struct loop *loop_i;
175   struct loop *loop_j;
176   unsigned int dependence_steps_i, dependence_steps_j;
177   unsigned int access_strides_i, access_strides_j;
178   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
179   struct data_dependence_relation *ddr;
180
181   if (VEC_length (ddr_p, dependence_relations) == 0)
182     return trans;
183
184   /* When there is an unknown relation in the dependence_relations, we
185      know that it is no worth looking at this loop nest: give up.  */
186   ddr = VEC_index (ddr_p, dependence_relations, 0);
187   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
188     return trans;
189   
190   /* LOOP_I is always the outer loop.  */
191   for (loop_j = first_loop->inner; 
192        loop_j; 
193        loop_j = loop_j->inner)
194     for (loop_i = first_loop; 
195          loop_i->depth < loop_j->depth; 
196          loop_i = loop_i->inner)
197       {
198         gather_interchange_stats (dependence_relations, datarefs,
199                                   loop_i, first_loop,
200                                   &dependence_steps_i, 
201                                   &nb_deps_not_carried_by_i,
202                                   &access_strides_i);
203         gather_interchange_stats (dependence_relations, datarefs,
204                                   loop_j, first_loop,
205                                   &dependence_steps_j, 
206                                   &nb_deps_not_carried_by_j, 
207                                   &access_strides_j);
208         
209         /* Heuristics for loop interchange profitability:
210
211            1. (spatial locality) Inner loops should have smallest
212               dependence steps.
213
214            2. (spatial locality) Inner loops should contain more
215            dependence relations not carried by the loop.
216
217            3. (temporal locality) Inner loops should have smallest 
218               array access strides.
219         */
220         if (dependence_steps_i < dependence_steps_j 
221             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
222             || access_strides_i < access_strides_j)
223           {
224             lambda_matrix_row_exchange (LTM_MATRIX (trans),
225                                         loop_i->depth - first_loop->depth,
226                                         loop_j->depth - first_loop->depth);
227             /* Validate the resulting matrix.  When the transformation
228                is not valid, reverse to the previous transformation.  */
229             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
230               lambda_matrix_row_exchange (LTM_MATRIX (trans), 
231                                           loop_i->depth - first_loop->depth, 
232                                           loop_j->depth - first_loop->depth);
233           }
234       }
235
236   return trans;
237 }
238
239 /* Perform a set of linear transforms on loops.  */
240
241 void
242 linear_transform_loops (void)
243 {
244   bool modified = false;
245   loop_iterator li;
246   VEC(tree,heap) *oldivs = NULL;
247   VEC(tree,heap) *invariants = NULL;
248   struct loop *loop_nest;
249   
250   FOR_EACH_LOOP (li, loop_nest, 0)
251     {
252       unsigned int depth = 0;
253       VEC (ddr_p, heap) *dependence_relations;
254       VEC (data_reference_p, heap) *datarefs;
255       struct loop *temp;
256       lambda_loopnest before, after;
257       lambda_trans_matrix trans;
258       bool problem = false;
259       /* If it's not a loop nest, we don't want it.
260          We also don't handle sibling loops properly, 
261          which are loops of the following form:
262          for (i = 0; i < 50; i++)
263            {
264              for (j = 0; j < 50; j++)
265                {
266                 ...
267                }
268              for (j = 0; j < 50; j++)
269                {
270                 ...
271                }
272            } */
273       if (!loop_nest->inner || !single_exit (loop_nest))
274         continue;
275       VEC_truncate (tree, oldivs, 0);
276       VEC_truncate (tree, invariants, 0);
277       depth = 1;
278       for (temp = loop_nest->inner; temp; temp = temp->inner)
279         {
280           /* If we have a sibling loop or multiple exit edges, jump ship.  */
281           if (temp->next || !single_exit (temp))
282             {
283               problem = true;
284               break;
285             }
286           depth ++;
287         }
288       if (problem)
289         continue;
290
291       /* Analyze data references and dependence relations using scev.  */      
292  
293       datarefs = VEC_alloc (data_reference_p, heap, 10);
294       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
295       compute_data_dependences_for_loop (loop_nest, true, &datarefs,
296                                          &dependence_relations);
297
298       if (dump_file && (dump_flags & TDF_DETAILS))
299         dump_ddrs (dump_file, dependence_relations);
300
301       /* Build the transformation matrix.  */
302       trans = lambda_trans_matrix_new (depth, depth);
303       lambda_matrix_id (LTM_MATRIX (trans), depth);
304       trans = try_interchange_loops (trans, depth, dependence_relations,
305                                      datarefs, loop_nest);
306
307       if (lambda_trans_matrix_id_p (trans))
308         {
309           if (dump_file)
310            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
311           goto free_and_continue;
312         }
313
314       /* Check whether the transformation is legal.  */
315       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
316         {
317           if (dump_file)
318             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
319           goto free_and_continue;
320         }
321
322       before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
323                                                 &invariants);
324
325       if (!before)
326         goto free_and_continue;
327
328       if (dump_file)
329         {
330           fprintf (dump_file, "Before:\n");
331           print_lambda_loopnest (dump_file, before, 'i');
332         }
333   
334       after = lambda_loopnest_transform (before, trans);
335
336       if (dump_file)
337         {
338           fprintf (dump_file, "After:\n");
339           print_lambda_loopnest (dump_file, after, 'u');
340         }
341
342       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
343                                        after, trans);
344       modified = true;
345
346       if (dump_file)
347         fprintf (dump_file, "Successfully transformed loop.\n");
348
349     free_and_continue:
350       free_dependence_relations (dependence_relations);
351       free_data_refs (datarefs);
352     }
353
354   VEC_free (tree, heap, oldivs);
355   VEC_free (tree, heap, invariants);
356   scev_reset ();
357
358   if (modified)
359     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
360 }