OSDN Git Service

bf353e59f5b4ba99e8f1ee1e35a2c59e4795ad8c
[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   /* When there is an unknown relation in the dependence_relations, we
182      know that it is no worth looking at this loop nest: give up.  */
183   ddr = VEC_index (ddr_p, dependence_relations, 0);
184   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
185     return trans;
186   
187   /* LOOP_I is always the outer loop.  */
188   for (loop_j = first_loop->inner; 
189        loop_j; 
190        loop_j = loop_j->inner)
191     for (loop_i = first_loop; 
192          loop_i->depth < loop_j->depth; 
193          loop_i = loop_i->inner)
194       {
195         gather_interchange_stats (dependence_relations, datarefs,
196                                   loop_i, first_loop,
197                                   &dependence_steps_i, 
198                                   &nb_deps_not_carried_by_i,
199                                   &access_strides_i);
200         gather_interchange_stats (dependence_relations, datarefs,
201                                   loop_j, first_loop,
202                                   &dependence_steps_j, 
203                                   &nb_deps_not_carried_by_j, 
204                                   &access_strides_j);
205         
206         /* Heuristics for loop interchange profitability:
207
208            1. (spatial locality) Inner loops should have smallest
209               dependence steps.
210
211            2. (spatial locality) Inner loops should contain more
212            dependence relations not carried by the loop.
213
214            3. (temporal locality) Inner loops should have smallest 
215               array access strides.
216         */
217         if (dependence_steps_i < dependence_steps_j 
218             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
219             || access_strides_i < access_strides_j)
220           {
221             lambda_matrix_row_exchange (LTM_MATRIX (trans),
222                                         loop_i->depth - first_loop->depth,
223                                         loop_j->depth - first_loop->depth);
224             /* Validate the resulting matrix.  When the transformation
225                is not valid, reverse to the previous transformation.  */
226             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
227               lambda_matrix_row_exchange (LTM_MATRIX (trans), 
228                                           loop_i->depth - first_loop->depth, 
229                                           loop_j->depth - first_loop->depth);
230           }
231       }
232
233   return trans;
234 }
235
236 /* Perform a set of linear transforms on LOOPS.  */
237
238 void
239 linear_transform_loops (struct loops *loops)
240 {
241   unsigned int i;
242   VEC(tree,heap) *oldivs = NULL;
243   VEC(tree,heap) *invariants = NULL;
244   
245   for (i = 1; i < loops->num; i++)
246     {
247       unsigned int depth = 0;
248       VEC (ddr_p, heap) *dependence_relations;
249       VEC (data_reference_p, heap) *datarefs;
250       struct loop *loop_nest = loops->parray[i];
251       struct loop *temp;
252       lambda_loopnest before, after;
253       lambda_trans_matrix trans;
254       bool problem = false;
255       bool need_perfect_nest = false;
256       /* If it's not a loop nest, we don't want it.
257          We also don't handle sibling loops properly, 
258          which are loops of the following form:
259          for (i = 0; i < 50; i++)
260            {
261              for (j = 0; j < 50; j++)
262                {
263                 ...
264                }
265            for (j = 0; j < 50; j++)
266                {
267                 ...
268                }
269            } */
270       if (!loop_nest || !loop_nest->inner)
271         continue;
272       VEC_truncate (tree, oldivs, 0);
273       VEC_truncate (tree, invariants, 0);
274       depth = 1;
275       for (temp = loop_nest->inner; temp; temp = temp->inner)
276         {
277           /* If we have a sibling loop or multiple exit edges, jump ship.  */
278           if (temp->next || !temp->single_exit)
279             {
280               problem = true;
281               break;
282             }
283           depth ++;
284         }
285       if (problem)
286         continue;
287
288       /* Analyze data references and dependence relations using scev.  */      
289  
290       datarefs = VEC_alloc (data_reference_p, heap, 10);
291       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
292       compute_data_dependences_for_loop (loop_nest, true, &datarefs,
293                                          &dependence_relations);
294
295       if (dump_file && (dump_flags & TDF_DETAILS))
296         dump_ddrs (dump_file, dependence_relations);
297
298       /* Build the transformation matrix.  */
299       trans = lambda_trans_matrix_new (depth, depth);
300       lambda_matrix_id (LTM_MATRIX (trans), depth);
301       trans = try_interchange_loops (trans, depth, dependence_relations,
302                                      datarefs, loop_nest);
303
304       if (lambda_trans_matrix_id_p (trans))
305         {
306           if (dump_file)
307            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
308           continue;
309         }
310
311       /* Check whether the transformation is legal.  */
312       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
313         {
314           if (dump_file)
315             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
316           continue;
317         }
318
319       if (!perfect_nest_p (loop_nest))
320         need_perfect_nest = true;
321
322       before = gcc_loopnest_to_lambda_loopnest (loops,
323                                                 loop_nest, &oldivs, 
324                                                 &invariants,
325                                                 need_perfect_nest);
326       if (!before)
327         continue;
328             
329       if (dump_file)
330         {
331           fprintf (dump_file, "Before:\n");
332           print_lambda_loopnest (dump_file, before, 'i');
333         }
334   
335       after = lambda_loopnest_transform (before, trans);
336
337       if (dump_file)
338         {
339           fprintf (dump_file, "After:\n");
340           print_lambda_loopnest (dump_file, after, 'u');
341         }
342
343       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
344                                        after, trans);
345
346       if (dump_file)
347         fprintf (dump_file, "Successfully transformed loop.\n");
348
349       free_dependence_relations (dependence_relations);
350       free_data_refs (datarefs);
351     }
352
353   VEC_free (tree, heap, oldivs);
354   VEC_free (tree, heap, invariants);
355   scev_reset ();
356   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
357 }