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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [graphite-blocking.c] - Blame information for rev 745

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Heuristics and transform for loop blocking and strip mining on
2
   polyhedral representation.
3
 
4
   Copyright (C) 2009, 2010 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 "tree-flow.h"
27
#include "tree-dump.h"
28
#include "cfgloop.h"
29
#include "tree-chrec.h"
30
#include "tree-data-ref.h"
31
#include "sese.h"
32
 
33
#ifdef HAVE_cloog
34
#include "ppl_c.h"
35
#include "graphite-ppl.h"
36
#include "graphite-poly.h"
37
 
38
 
39
/* Strip mines with a factor STRIDE the scattering (time) dimension
40
   around PBB at depth TIME_DEPTH.
41
 
42
   The following example comes from the wiki page:
43
   http://gcc.gnu.org/wiki/Graphite/Strip_mine
44
 
45
   The strip mine of a loop with a tile of 64 can be obtained with a
46
   scattering function as follows:
47
 
48
   $ cat ./albert_strip_mine.cloog
49
   # language: C
50
   c
51
 
52
   # parameter {n | n >= 0}
53
   1 3
54
   #  n  1
55
   1  1  0
56
   1
57
   n
58
 
59
   1 # Number of statements:
60
 
61
   1
62
   # {i | 0 <= i <= n}
63
   2 4
64
   #  i  n   1
65
   1  1  0   0
66
   1 -1  1   0
67
 
68
 
69
   1
70
   i
71
 
72
   1 # Scattering functions
73
 
74
   3 6
75
   #  NEW  OLD    i    n    1
76
   1  -64    0    1    0    0
77
   1   64    0   -1    0   63
78
 
79
 
80
   1
81
   NEW  OLD
82
 
83
   #the output of CLooG is like this:
84
   #$ cloog ./albert_strip_mine.cloog
85
   # for (NEW=0;NEW<=floord(n,64);NEW++) {
86
   #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
87
   #     S1(i = OLD) ;
88
   #   }
89
   # }
90
*/
91
 
92
static void
93
pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
94
{
95
  ppl_dimension_type iter, dim, strip;
96
  ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
97
  /* STRIP is the dimension that iterates with stride STRIDE.  */
98
  /* ITER is the dimension that enumerates single iterations inside
99
     one strip that has at most STRIDE iterations.  */
100
  strip = time_depth;
101
  iter = strip + 2;
102
 
103
  psct_add_scattering_dimension (pbb, strip);
104
  psct_add_scattering_dimension (pbb, strip + 1);
105
 
106
  ppl_Polyhedron_space_dimension (res, &dim);
107
 
108
  /* Lower bound of the striped loop.  */
109
  {
110
    ppl_Constraint_t new_cstr;
111
    ppl_Linear_Expression_t expr;
112
 
113
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
114
    ppl_set_coef (expr, strip, -1 * stride);
115
    ppl_set_coef (expr, iter, 1);
116
 
117
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
118
    ppl_delete_Linear_Expression (expr);
119
    ppl_Polyhedron_add_constraint (res, new_cstr);
120
    ppl_delete_Constraint (new_cstr);
121
  }
122
 
123
  /* Upper bound of the striped loop.  */
124
  {
125
    ppl_Constraint_t new_cstr;
126
    ppl_Linear_Expression_t expr;
127
 
128
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
129
    ppl_set_coef (expr, strip, stride);
130
    ppl_set_coef (expr, iter, -1);
131
    ppl_set_inhomogeneous (expr, stride - 1);
132
 
133
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
134
    ppl_delete_Linear_Expression (expr);
135
    ppl_Polyhedron_add_constraint (res, new_cstr);
136
    ppl_delete_Constraint (new_cstr);
137
  }
138
 
139
  /* Static scheduling for ITER level.
140
     This is mandatory to keep the 2d + 1 canonical scheduling format.  */
141
  {
142
    ppl_Constraint_t new_cstr;
143
    ppl_Linear_Expression_t expr;
144
 
145
    ppl_new_Linear_Expression_with_dimension (&expr, dim);
146
    ppl_set_coef (expr, strip + 1, 1);
147
    ppl_set_inhomogeneous (expr, 0);
148
 
149
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
150
    ppl_delete_Linear_Expression (expr);
151
    ppl_Polyhedron_add_constraint (res, new_cstr);
152
    ppl_delete_Constraint (new_cstr);
153
  }
154
}
155
 
156
/* Returns true when strip mining with STRIDE of the loop LST is
157
   profitable.  */
158
 
159
static bool
160
lst_strip_mine_profitable_p (lst_p lst, int stride)
161
{
162
  mpz_t niter, strip_stride;
163
  bool res;
164
 
165
  gcc_assert (LST_LOOP_P (lst));
166
  mpz_init (strip_stride);
167
  mpz_init (niter);
168
 
169
  mpz_set_si (strip_stride, stride);
170
  lst_niter_for_loop (lst, niter);
171
  res = (mpz_cmp (niter, strip_stride) > 0);
172
 
173
  mpz_clear (strip_stride);
174
  mpz_clear (niter);
175
  return res;
176
}
177
 
178
/* Strip-mines all the loops of LST with STRIDE.  Return the number of
179
   loops strip-mined.  */
180
 
181
static int
182
lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
183
{
184
  int i;
185
  lst_p l;
186
  poly_bb_p pbb;
187
 
188
  if (!lst)
189
    return 0;
190
 
191
  if (LST_LOOP_P (lst))
192
    {
193
      int res = 0;
194
 
195
      FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
196
        res += lst_do_strip_mine_loop (l, depth, stride);
197
 
198
      return res;
199
    }
200
 
201
  pbb = LST_PBB (lst);
202
  pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride);
203
  return 1;
204
}
205
 
206
/* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
207
   read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return the
208
   number of strip-mined loops.
209
 
210
   Strip mining transforms a loop
211
 
212
   | for (i = 0; i < N; i++)
213
   |   S (i);
214
 
215
   into the following loop nest:
216
 
217
   | for (k = 0; k < N; k += STRIDE)
218
   |   for (j = 0; j < STRIDE; j++)
219
   |     S (i = k + j);
220
*/
221
 
222
static int
223
lst_do_strip_mine (lst_p lst, int stride)
224
{
225
  int i;
226
  lst_p l;
227
  int res = 0;
228
  int depth;
229
 
230
  if (!stride)
231
    stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
232
 
233
  if (!lst
234
      || !LST_LOOP_P (lst))
235
    return false;
236
 
237
  FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
238
    res += lst_do_strip_mine (l, stride);
239
 
240
  depth = lst_depth (lst);
241
  if (depth >= 0
242
      && lst_strip_mine_profitable_p (lst, stride))
243
    {
244
      res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
245
      lst_add_loop_under_loop (lst);
246
    }
247
 
248
  return res;
249
}
250
 
251
/* Strip mines all the loops in SCOP.  Returns the number of
252
   strip-mined loops.  */
253
 
254
int
255
scop_do_strip_mine (scop_p scop, int stride)
256
{
257
  return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
258
}
259
 
260
/* Loop blocks all the loops in SCOP.  Returns true when we manage to
261
   block some loops.  */
262
 
263
bool
264
scop_do_block (scop_p scop)
265
{
266
  store_scattering (scop);
267
 
268
  /* If we don't strip mine at least two loops, or not interchange
269
     loops, the strip mine alone will not be profitable, and the
270
     transform is not a loop blocking: so revert the transform.  */
271
  if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2
272
      || scop_do_interchange (scop) == 0)
273
    {
274
      restore_scattering (scop);
275
      return false;
276
    }
277
 
278
  if (dump_file && (dump_flags & TDF_DETAILS))
279
    fprintf (dump_file, "SCoP will be loop blocked.\n");
280
 
281
  return true;
282
}
283
 
284
#endif

powered by: WebSVN 2.1.0

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