OSDN Git Service

2004-10-16 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.  LOOP_NUMBER is a relative
59    index in the considered loop nest.  The first loop in the
60    considered loop nest is FIRST_LOOP, and consequently the index of
61    the considered loop is obtained by FIRST_LOOP + LOOP_NUMBER.
62    
63    Initializes:
64    - DEPENDENCE_STEPS the sum of all the data dependence distances
65    carried by loop LOOP_NUMBER,
66
67    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
68    for which the loop LOOP_NUMBER is not carrying any dependence,
69
70    - ACCESS_STRIDES the sum of all the strides in LOOP_NUMBER.
71
72    Example: for the following loop,
73
74    | loop_1 runs 1335 times
75    |   loop_2 runs 1335 times
76    |     A[{{0, +, 1}_1, +, 1335}_2]
77    |     B[{{0, +, 1}_1, +, 1335}_2]
78    |   endloop_2
79    |   A[{0, +, 1336}_1]
80    | endloop_1
81
82    gather_interchange_stats (in loop_1) will return 
83    DEPENDENCE_STEPS = 3002
84    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
85    ACCESS_STRIDES = 10694
86
87    gather_interchange_stats (in loop_2) will return 
88    DEPENDENCE_STEPS = 3000
89    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
90    ACCESS_STRIDES = 8010
91   */
92
93 static void
94 gather_interchange_stats (varray_type dependence_relations, 
95                           varray_type datarefs,
96                           unsigned int loop_number, 
97                           unsigned int first_loop,
98                           unsigned int *dependence_steps, 
99                           unsigned int *nb_deps_not_carried_by_loop, 
100                           unsigned int *access_strides)
101 {
102   unsigned int i;
103
104   *dependence_steps = 0;
105   *nb_deps_not_carried_by_loop = 0;
106   *access_strides = 0;
107
108   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
109     {
110       int dist;
111       struct data_dependence_relation *ddr = 
112         (struct data_dependence_relation *) 
113         VARRAY_GENERIC_PTR (dependence_relations, i);
114
115       /* Compute the dependence strides.  */
116
117       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
118         {
119           (*dependence_steps) += 0;
120           continue;
121         }
122
123       /* When we know that there is no dependence, we know that there
124          is no reuse of the data.  */
125       if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
126         {
127           (*dependence_steps) += 0;
128           continue;
129         }
130       dist = DDR_DIST_VECT (ddr)[loop_number];
131       if (dist == 0)
132         (*nb_deps_not_carried_by_loop) += 1;
133       else if (dist < 0)
134         (*dependence_steps) += -dist;
135       else
136         (*dependence_steps) += dist;
137     }
138
139   /* Compute the access strides.  */
140   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
141     {
142       unsigned int it;
143       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
144       tree stmt = DR_STMT (dr);
145       struct loop *stmt_loop = loop_containing_stmt (stmt);
146       struct loop *inner_loop = current_loops->parray[first_loop + 1];
147
148       if (!flow_loop_nested_p (inner_loop, stmt_loop)
149           && inner_loop->num != stmt_loop->num)
150         continue;
151
152       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
153         {
154           tree chrec = DR_ACCESS_FN (dr, it);
155           tree tstride = evolution_part_in_loop_num 
156             (chrec, first_loop + loop_number);
157           
158           if (tstride == NULL_TREE
159               || TREE_CODE (tstride) != INTEGER_CST)
160             continue;
161           
162           (*access_strides) += int_cst_value (tstride);
163         }
164     }
165 }
166
167 /* Apply to TRANS any loop interchange that minimize inner loop steps.
168    Returns the new transform matrix.  The smaller the reuse vector
169    distances in the inner loops, the fewer the cache misses.
170    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
171    nest.  */
172
173
174 static lambda_trans_matrix
175 try_interchange_loops (lambda_trans_matrix trans, 
176                        unsigned int depth,                     
177                        varray_type dependence_relations,
178                        varray_type datarefs, 
179                        unsigned int first_loop)
180 {
181   unsigned int loop_i, loop_j;
182   unsigned int dependence_steps_i, dependence_steps_j;
183   unsigned int access_strides_i, access_strides_j;
184   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
185   struct data_dependence_relation *ddr;
186
187   /* When there is an unknown relation in the dependence_relations, we
188      know that it is no worth looking at this loop nest: give up.  */
189   ddr = (struct data_dependence_relation *) 
190     VARRAY_GENERIC_PTR (dependence_relations, 0);
191   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
192     return trans;
193   
194   /* LOOP_I is always the outer loop.  */
195   for (loop_j = 1; loop_j < depth; loop_j++)
196     for (loop_i = 0; loop_i < loop_j; loop_i++)
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), loop_i, loop_j);
225             /* Validate the resulting matrix.  When the transformation
226                is not valid, reverse to the previous transformation.  */
227             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
228               lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
229           }
230       }
231
232   return trans;
233 }
234
235 /* Perform a set of linear transforms on LOOPS.  */
236
237 void
238 linear_transform_loops (struct loops *loops)
239 {
240   unsigned int i;
241
242   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
243   for (i = 1; i < loops->num; i++)
244     {
245       unsigned int depth = 0;
246       varray_type datarefs;
247       varray_type dependence_relations;
248       struct loop *loop_nest = loops->parray[i];
249       struct loop *temp;
250       VEC (tree) *oldivs = NULL;
251       VEC (tree) *invariants = NULL;
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->inner)
271         continue;
272       depth = 1;
273       for (temp = loop_nest->inner; temp; temp = temp->inner)
274         {
275           flow_loop_scan (temp, LOOP_ALL);
276           /* If we have a sibling loop or multiple exit edges, jump ship.  */
277           if (temp->next || temp->num_exits != 1)
278             {
279               problem = true;
280               break;
281             }
282           depth ++;
283         }
284       if (problem)
285         continue;
286
287       /* Analyze data references and dependence relations using scev.  */      
288  
289       VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
290       VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
291                                "dependence_relations");
292       
293   
294       compute_data_dependences_for_loop (depth, loop_nest,
295                                          &datarefs, &dependence_relations);
296       if (dump_file && (dump_flags & TDF_DETAILS))
297         {
298           unsigned int j;
299           for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
300             {
301               struct data_dependence_relation *ddr = 
302                 (struct data_dependence_relation *) 
303                 VARRAY_GENERIC_PTR (dependence_relations, j);
304
305               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
306                 {
307                   fprintf (dump_file, "DISTANCE_V (");
308                   print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), 
309                                        DDR_SIZE_VECT (ddr));
310                   fprintf (dump_file, ")\n");
311                   fprintf (dump_file, "DIRECTION_V (");
312                   print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), 
313                                        DDR_SIZE_VECT (ddr));
314                   fprintf (dump_file, ")\n");
315                 }
316             }
317           fprintf (dump_file, "\n\n");
318         }
319       /* Build the transformation matrix.  */
320       trans = lambda_trans_matrix_new (depth, depth);
321       lambda_matrix_id (LTM_MATRIX (trans), depth);
322
323       trans = try_interchange_loops (trans, depth, dependence_relations,
324                                      datarefs, loop_nest->num);
325
326       if (lambda_trans_matrix_id_p (trans))
327         {
328           if (dump_file)
329            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
330           continue;
331         }
332
333       /* Check whether the transformation is legal.  */
334       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
335         {
336           if (dump_file)
337             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
338           continue;
339         }
340       if (!perfect_nest_p (loop_nest))
341         need_perfect_nest = true;
342       before = gcc_loopnest_to_lambda_loopnest (loops,
343                                                 loop_nest, &oldivs, 
344                                                 &invariants,
345                                                 need_perfect_nest);
346       if (!before)
347         continue;
348             
349       if (dump_file)
350         {
351           fprintf (dump_file, "Before:\n");
352           print_lambda_loopnest (dump_file, before, 'i');
353         }
354   
355       after = lambda_loopnest_transform (before, trans);
356       if (dump_file)
357         {
358           fprintf (dump_file, "After:\n");
359           print_lambda_loopnest (dump_file, after, 'u');
360         }
361       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
362                                        after, trans);
363       if (dump_file)
364         fprintf (dump_file, "Successfully transformed loop.\n");
365       oldivs = NULL;
366       invariants = NULL;
367       free_dependence_relations (dependence_relations);
368       free_data_refs (datarefs);
369     }
370   free_df ();
371   scev_reset ();
372   rewrite_into_loop_closed_ssa ();
373 #ifdef ENABLE_CHECKING
374   verify_loop_closed_ssa ();
375 #endif
376 }