OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [graphite-blocking.c] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Heuristics and transform for loop blocking and strip mining on
2
   polyhedral representation.
3
 
4
   Copyright (C) 2009 Free Software Foundation, Inc.
5
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
6
   Pranav Garg  <pranav.garg2107@gmail.com>.
7
 
8
This file is part of GCC.
9
 
10
GCC is free software; you can redistribute it and/or modify
11
it under the terms of the GNU General Public License as published by
12
the Free Software Foundation; either version 3, or (at your option)
13
any later version.
14
 
15
GCC is distributed in the hope that it will be useful,
16
but WITHOUT ANY WARRANTY; without even the implied warranty of
17
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18
GNU General Public License for more details.
19
 
20
You should have received a copy of the GNU General Public License
21
along with GCC; see the file COPYING3.  If not see
22
<http://www.gnu.org/licenses/>.  */
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 "rtl.h"
30
#include "output.h"
31
#include "basic-block.h"
32
#include "diagnostic.h"
33
#include "tree-flow.h"
34
#include "toplev.h"
35
#include "tree-dump.h"
36
#include "timevar.h"
37
#include "cfgloop.h"
38
#include "tree-chrec.h"
39
#include "tree-data-ref.h"
40
#include "tree-scalar-evolution.h"
41
#include "tree-pass.h"
42
#include "domwalk.h"
43
#include "value-prof.h"
44
#include "pointer-set.h"
45
#include "gimple.h"
46
#include "params.h"
47
 
48
#ifdef HAVE_cloog
49
#include "cloog/cloog.h"
50
#include "ppl_c.h"
51
#include "sese.h"
52
#include "graphite-ppl.h"
53
#include "graphite.h"
54
#include "graphite-poly.h"
55
 
56
 
57
/* Strip mines with a factor STRIDE the scattering (time) dimension
58
   around PBB at depth TIME_DEPTH.
59
 
60
   The following example comes from the wiki page:
61
   http://gcc.gnu.org/wiki/Graphite/Strip_mine
62
 
63
   The strip mine of a loop with a tile of 64 can be obtained with a
64
   scattering function as follows:
65
 
66
   $ cat ./albert_strip_mine.cloog
67
   # language: C
68
   c
69
 
70
   # parameter {n | n >= 0}
71
   1 3
72
   #  n  1
73
   1  1  0
74
   1
75
   n
76
 
77
   1 # Number of statements:
78
 
79
   1
80
   # {i | 0 <= i <= n}
81
   2 4
82
   #  i  n   1
83
   1  1  0   0
84
   1 -1  1   0
85
 
86
 
87
   1
88
   i
89
 
90
   1 # Scattering functions
91
 
92
   3 6
93
   #  NEW  OLD    i    n    1
94
   1  -64    0    1    0    0
95
   1   64    0   -1    0   63
96
 
97
 
98
   1
99
   NEW  OLD
100
 
101
   #the output of CLooG is like this:
102
   #$ cloog ./albert_strip_mine.cloog
103
   # for (NEW=0;NEW<=floord(n,64);NEW++) {
104
   #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
105
   #     S1(i = OLD) ;
106
   #   }
107
   # }
108
*/
109
 
110
static bool
111
pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
112
{
113
  ppl_dimension_type iter, dim, strip;
114
  ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
115
  /* STRIP is the dimension that iterates with stride STRIDE.  */
116
  /* ITER is the dimension that enumerates single iterations inside
117
     one strip that has at most STRIDE iterations.  */
118
  strip = time_depth;
119
  iter = strip + 2;
120
 
121
  psct_add_scattering_dimension (pbb, strip);
122
  psct_add_scattering_dimension (pbb, strip + 1);
123
 
124
  ppl_Polyhedron_space_dimension (res, &dim);
125
 
126
  /* Lower bound of the striped loop.  */
127
  {
128
    ppl_Constraint_t new_cstr;
129
    ppl_Linear_Expression_t expr;
130
 
131
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
132
    ppl_set_coef (expr, strip, -1 * stride);
133
    ppl_set_coef (expr, iter, 1);
134
 
135
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
136
    ppl_delete_Linear_Expression (expr);
137
    ppl_Polyhedron_add_constraint (res, new_cstr);
138
    ppl_delete_Constraint (new_cstr);
139
  }
140
 
141
  /* Upper bound of the striped loop.  */
142
  {
143
    ppl_Constraint_t new_cstr;
144
    ppl_Linear_Expression_t expr;
145
 
146
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
147
    ppl_set_coef (expr, strip, stride);
148
    ppl_set_coef (expr, iter, -1);
149
    ppl_set_inhomogeneous (expr, stride - 1);
150
 
151
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
152
    ppl_delete_Linear_Expression (expr);
153
    ppl_Polyhedron_add_constraint (res, new_cstr);
154
    ppl_delete_Constraint (new_cstr);
155
  }
156
 
157
  /* Static scheduling for ITER level.
158
     This is mandatory to keep the 2d + 1 canonical scheduling format.  */
159
  {
160
    ppl_Constraint_t new_cstr;
161
    ppl_Linear_Expression_t expr;
162
 
163
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
164
    ppl_set_coef (expr, strip + 1, 1);
165
    ppl_set_inhomogeneous (expr, 0);
166
 
167
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
168
    ppl_delete_Linear_Expression (expr);
169
    ppl_Polyhedron_add_constraint (res, new_cstr);
170
    ppl_delete_Constraint (new_cstr);
171
  }
172
 
173
  return true;
174
}
175
 
176
/* Returns true when strip mining with STRIDE of the loop around PBB
177
   at DEPTH is profitable.  */
178
 
179
static bool
180
pbb_strip_mine_profitable_p (poly_bb_p pbb,
181
                             graphite_dim_t depth,
182
                             int stride)
183
{
184
  Value niter, strip_stride;
185
  bool res;
186
 
187
  value_init (strip_stride);
188
  value_init (niter);
189
  value_set_si (strip_stride, stride);
190
  pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
191
  res = value_gt (niter, strip_stride);
192
  value_clear (strip_stride);
193
  value_clear (niter);
194
 
195
  return res;
196
}
197
 
198
/* Strip-mines all the loops of LST that are considered profitable to
199
   strip-mine.  Return true if it did strip-mined some loops.  */
200
 
201
static bool
202
lst_do_strip_mine_loop (lst_p lst, int depth)
203
{
204
  int i;
205
  lst_p l;
206
  int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
207
  poly_bb_p pbb;
208
 
209
  if (!lst)
210
    return false;
211
 
212
  if (LST_LOOP_P (lst))
213
    {
214
      bool res = false;
215
 
216
      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
217
        res |= lst_do_strip_mine_loop (l, depth);
218
 
219
      return res;
220
    }
221
 
222
  pbb = LST_PBB (lst);
223
  return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
224
                                    stride);
225
}
226
 
227
/* Strip-mines all the loops of LST that are considered profitable to
228
   strip-mine.  Return true if it did strip-mined some loops.  */
229
 
230
static bool
231
lst_do_strip_mine (lst_p lst)
232
{
233
  int i;
234
  lst_p l;
235
  bool res = false;
236
  int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
237
  int depth;
238
 
239
  if (!lst
240
      || !LST_LOOP_P (lst))
241
    return false;
242
 
243
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
244
    res |= lst_do_strip_mine (l);
245
 
246
  depth = lst_depth (lst);
247
  if (depth >= 0
248
      && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst)),
249
                                      depth, stride))
250
    {
251
      res |= lst_do_strip_mine_loop (lst, lst_depth (lst));
252
      lst_add_loop_under_loop (lst);
253
    }
254
 
255
  return res;
256
}
257
 
258
/* Strip mines all the loops in SCOP.  Nothing profitable in all this:
259
   this is just a driver function.  */
260
 
261
bool
262
scop_do_strip_mine (scop_p scop)
263
{
264
  bool transform_done = false;
265
 
266
  store_scattering (scop);
267
 
268
  transform_done = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
269
 
270
  if (!transform_done)
271
    return false;
272
 
273
  if (!graphite_legal_transform (scop))
274
    {
275
      restore_scattering (scop);
276
      return false;
277
    }
278
 
279
  return transform_done;
280
}
281
 
282
/* Loop blocks all the loops in SCOP.  Returns true when we manage to
283
   block some loops.  */
284
 
285
bool
286
scop_do_block (scop_p scop)
287
{
288
  bool strip_mined = false;
289
  bool interchanged = false;
290
 
291
  store_scattering (scop);
292
 
293
  strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
294
  interchanged = scop_do_interchange (scop);
295
 
296
  /* If we don't interchange loops, then the strip mine is not
297
     profitable, and the transform is not a loop blocking.  */
298
  if (!interchanged
299
      || !graphite_legal_transform (scop))
300
    {
301
      restore_scattering (scop);
302
      return false;
303
    }
304
  else if (strip_mined && interchanged
305
           && dump_file && (dump_flags & TDF_DETAILS))
306
    fprintf (dump_file, "SCoP will be loop blocked.\n");
307
 
308
  return strip_mined || interchanged;
309
}
310
 
311
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.