OSDN Git Service

* basic-block.h, c-common.c, c-cppbuiltin.c, c-lang.c,
[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, 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 is the loop being
59    considered. The first loop in the considered loop nest is
60    FIRST_LOOP, and consequently, the index of the considered loop is
61    obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
62    
63    Initializes:
64    - DEPENDENCE_STEPS the sum of all the data dependence distances
65    carried by loop LOOP,
66
67    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
68    for which the loop LOOP is not carrying any dependence,
69
70    - ACCESS_STRIDES the sum of all the strides in LOOP.
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                           struct loop *loop,
97                           struct loop *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       /* If we don't know anything about this dependence, or the distance
116          vector is NULL, or there is no dependence, then there is no reuse of
117          data.  */
118
119       if (DDR_DIST_VECT (ddr) == NULL
120           || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
121           || DDR_ARE_DEPENDENT (ddr) == chrec_known)
122         continue;
123       
124
125       
126       dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
127       if (dist == 0)
128         (*nb_deps_not_carried_by_loop) += 1;
129       else if (dist < 0)
130         (*dependence_steps) += -dist;
131       else
132         (*dependence_steps) += dist;
133     }
134
135   /* Compute the access strides.  */
136   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
137     {
138       unsigned int it;
139       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
140       tree stmt = DR_STMT (dr);
141       struct loop *stmt_loop = loop_containing_stmt (stmt);
142       struct loop *inner_loop = first_loop->inner;
143       
144       if (inner_loop != stmt_loop 
145           && !flow_loop_nested_p (inner_loop, stmt_loop))
146         continue;
147       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
148         {
149           tree chrec = DR_ACCESS_FN (dr, it);
150           tree tstride = evolution_part_in_loop_num 
151             (chrec, loop->num);
152           
153           if (tstride == NULL_TREE
154               || TREE_CODE (tstride) != INTEGER_CST)
155             continue;
156           
157           (*access_strides) += int_cst_value (tstride);
158         }
159     }
160 }
161
162 /* Attempt to apply interchange transformations to TRANS to maximize the
163    spatial and temporal locality of the loop.  
164    Returns the new transform matrix.  The smaller the reuse vector
165    distances in the inner loops, the fewer the cache misses.
166    FIRST_LOOP is the loop->num of the first loop in the analyzed loop
167    nest.  */
168
169
170 static lambda_trans_matrix
171 try_interchange_loops (lambda_trans_matrix trans, 
172                        unsigned int depth,                     
173                        varray_type dependence_relations,
174                        varray_type datarefs, 
175                        struct loop *first_loop)
176 {
177   struct loop *loop_i;
178   struct loop *loop_j;
179   unsigned int dependence_steps_i, dependence_steps_j;
180   unsigned int access_strides_i, access_strides_j;
181   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
182   struct data_dependence_relation *ddr;
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 = (struct data_dependence_relation *) 
187     VARRAY_GENERIC_PTR (dependence_relations, 0);
188   if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
189     return trans;
190   
191   /* LOOP_I is always the outer loop.  */
192   for (loop_j = first_loop->inner; 
193        loop_j; 
194        loop_j = loop_j->inner)
195     for (loop_i = first_loop; 
196          loop_i->depth < loop_j->depth; 
197          loop_i = loop_i->inner)
198       {
199         gather_interchange_stats (dependence_relations, datarefs,
200                                   loop_i, first_loop,
201                                   &dependence_steps_i, 
202                                   &nb_deps_not_carried_by_i,
203                                   &access_strides_i);
204         gather_interchange_stats (dependence_relations, datarefs,
205                                   loop_j, first_loop,
206                                   &dependence_steps_j, 
207                                   &nb_deps_not_carried_by_j, 
208                                   &access_strides_j);
209         
210         /* Heuristics for loop interchange profitability:
211
212            1. (spatial locality) Inner loops should have smallest
213               dependence steps.
214
215            2. (spatial locality) Inner loops should contain more
216            dependence relations not carried by the loop.
217
218            3. (temporal locality) Inner loops should have smallest 
219               array access strides.
220         */
221         if (dependence_steps_i < dependence_steps_j 
222             || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
223             || access_strides_i < access_strides_j)
224           {
225             lambda_matrix_row_exchange (LTM_MATRIX (trans),
226                                         loop_i->depth - first_loop->depth,
227                                         loop_j->depth - first_loop->depth);
228             /* Validate the resulting matrix.  When the transformation
229                is not valid, reverse to the previous transformation.  */
230             if (!lambda_transform_legal_p (trans, depth, dependence_relations))
231               lambda_matrix_row_exchange (LTM_MATRIX (trans), 
232                                           loop_i->depth - first_loop->depth, 
233                                           loop_j->depth - first_loop->depth);
234           }
235       }
236
237   return trans;
238 }
239
240 /* Perform a set of linear transforms on LOOPS.  */
241
242 void
243 linear_transform_loops (struct loops *loops)
244 {
245   unsigned int i;
246   
247   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
248   for (i = 1; i < loops->num; i++)
249     {
250       unsigned int depth = 0;
251       varray_type datarefs;
252       varray_type dependence_relations;
253       struct loop *loop_nest = loops->parray[i];
254       struct loop *temp;
255       VEC (tree) *oldivs = NULL;
256       VEC (tree) *invariants = NULL;
257       lambda_loopnest before, after;
258       lambda_trans_matrix trans;
259       bool problem = false;
260       bool need_perfect_nest = false;
261       /* If it's not a loop nest, we don't want it.
262          We also don't handle sibling loops properly, 
263          which are loops of the following form:
264          for (i = 0; i < 50; i++)
265            {
266              for (j = 0; j < 50; j++)
267                {
268                 ...
269                }
270            for (j = 0; j < 50; j++)
271                {
272                 ...
273                }
274            } */
275       if (!loop_nest->inner)
276         continue;
277       depth = 1;
278       for (temp = loop_nest->inner; temp; temp = temp->inner)
279         {
280           flow_loop_scan (temp, LOOP_ALL);
281           /* If we have a sibling loop or multiple exit edges, jump ship.  */
282           if (temp->next || temp->num_exits != 1)
283             {
284               problem = true;
285               break;
286             }
287           depth ++;
288         }
289       if (problem)
290         continue;
291
292       /* Analyze data references and dependence relations using scev.  */      
293  
294       VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
295       VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
296                                "dependence_relations");
297       
298   
299       compute_data_dependences_for_loop (depth, loop_nest,
300                                          &datarefs, &dependence_relations);
301       if (dump_file && (dump_flags & TDF_DETAILS))
302         {
303           unsigned int j;
304           for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
305             {
306               struct data_dependence_relation *ddr = 
307                 (struct data_dependence_relation *) 
308                 VARRAY_GENERIC_PTR (dependence_relations, j);
309
310               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
311                 {
312                   fprintf (dump_file, "DISTANCE_V (");
313                   print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), 
314                                        DDR_SIZE_VECT (ddr));
315                   fprintf (dump_file, ")\n");
316                   fprintf (dump_file, "DIRECTION_V (");
317                   print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), 
318                                        DDR_SIZE_VECT (ddr));
319                   fprintf (dump_file, ")\n");
320                 }
321             }
322           fprintf (dump_file, "\n\n");
323         }
324       /* Build the transformation matrix.  */
325       trans = lambda_trans_matrix_new (depth, depth);
326       lambda_matrix_id (LTM_MATRIX (trans), depth);
327
328       trans = try_interchange_loops (trans, depth, dependence_relations,
329                                      datarefs, loop_nest);
330
331       if (lambda_trans_matrix_id_p (trans))
332         {
333           if (dump_file)
334            fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
335           continue;
336         }
337
338       /* Check whether the transformation is legal.  */
339       if (!lambda_transform_legal_p (trans, depth, dependence_relations))
340         {
341           if (dump_file)
342             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
343           continue;
344         }
345       if (!perfect_nest_p (loop_nest))
346         need_perfect_nest = true;
347       before = gcc_loopnest_to_lambda_loopnest (loops,
348                                                 loop_nest, &oldivs, 
349                                                 &invariants,
350                                                 need_perfect_nest);
351       if (!before)
352         continue;
353             
354       if (dump_file)
355         {
356           fprintf (dump_file, "Before:\n");
357           print_lambda_loopnest (dump_file, before, 'i');
358         }
359   
360       after = lambda_loopnest_transform (before, trans);
361       if (dump_file)
362         {
363           fprintf (dump_file, "After:\n");
364           print_lambda_loopnest (dump_file, after, 'u');
365         }
366       lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
367                                        after, trans);
368       if (dump_file)
369         fprintf (dump_file, "Successfully transformed loop.\n");
370       oldivs = NULL;
371       invariants = NULL;
372       free_dependence_relations (dependence_relations);
373       free_data_refs (datarefs);
374     }
375   free_df ();
376   scev_reset ();
377   rewrite_into_loop_closed_ssa ();
378 #ifdef ENABLE_CHECKING
379   verify_loop_closed_ssa ();
380 #endif
381 }