|
0
|
1 /* Gimple Represented as Polyhedra.
|
|
|
2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
|
|
|
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 it under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #ifndef GCC_GRAPHITE_H
|
|
|
22 #define GCC_GRAPHITE_H
|
|
|
23
|
|
|
24 #include "tree-data-ref.h"
|
|
|
25
|
|
|
26 int ref_nb_loops (data_reference_p);
|
|
|
27
|
|
|
28 typedef struct graphite_bb *graphite_bb_p;
|
|
|
29 DEF_VEC_P(graphite_bb_p);
|
|
|
30 DEF_VEC_ALLOC_P (graphite_bb_p, heap);
|
|
|
31
|
|
|
32 DEF_VEC_P(scop_p);
|
|
|
33 DEF_VEC_ALLOC_P (scop_p, heap);
|
|
|
34
|
|
|
35 static inline int scop_nb_loops (scop_p scop);
|
|
|
36 static inline unsigned scop_nb_params (scop_p scop);
|
|
|
37 static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
|
|
|
38
|
|
|
39 typedef struct graphite_bb
|
|
|
40 {
|
|
|
41 basic_block bb;
|
|
|
42 scop_p scop;
|
|
|
43
|
|
|
44 /* The static schedule contains the textual order for every loop layer.
|
|
|
45
|
|
|
46 Example:
|
|
|
47
|
|
|
48 S0
|
|
|
49 for (i ...)
|
|
|
50 {
|
|
|
51 S1
|
|
|
52 for (j ...)
|
|
|
53 {
|
|
|
54 S2
|
|
|
55 S3
|
|
|
56 }
|
|
|
57 S4
|
|
|
58 }
|
|
|
59 S5
|
|
|
60 for (k ...)
|
|
|
61 {
|
|
|
62 S6
|
|
|
63 S7
|
|
|
64 for (l ...)
|
|
|
65 {
|
|
|
66 S8
|
|
|
67 }
|
|
|
68 S9
|
|
|
69 }
|
|
|
70 S10
|
|
|
71
|
|
|
72 Schedules:
|
|
|
73
|
|
|
74 | Depth
|
|
|
75 BB | 0 1 2
|
|
|
76 ------------
|
|
|
77 S0 | 0
|
|
|
78 S1 | 1, 0
|
|
|
79 S2 | 1, 1, 0
|
|
|
80 S3 | 1, 1, 1
|
|
|
81 S4 | 1, 2
|
|
|
82 S5 | 2
|
|
|
83 S6 | 3, 0
|
|
|
84 S7 | 3, 1
|
|
|
85 S8 | 3, 2, 0
|
|
|
86 S9 | 3, 3
|
|
|
87 S10| 4
|
|
|
88
|
|
|
89 Normalization rules:
|
|
|
90 - One SCoP can never contain two bbs with the same schedule timestamp.
|
|
|
91 - All bbs at the same loop depth have a consecutive ordering (no gaps). */
|
|
|
92 lambda_vector static_schedule;
|
|
|
93
|
|
|
94 /* The iteration domain of this bb. It contains this columns:
|
|
|
95 - In/Eq: If this line is a equation or inequation.
|
|
|
96 - For every loop iterator one column.
|
|
|
97 - One column for every parameter in this SCoP.
|
|
|
98 - The constant column to add integers to the (in)equations.
|
|
|
99
|
|
|
100 Example:
|
|
|
101
|
|
|
102 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
|
|
|
103 for (j = 2; j <= 2*i + 5; j++)
|
|
|
104 for (k = 0; k <= 5; k++)
|
|
|
105 S (i,j,k)
|
|
|
106
|
|
|
107 Loop iterators: i, j, k
|
|
|
108 Parameters: a, b
|
|
|
109
|
|
|
110 (I)eq i j k a b 1
|
|
|
111
|
|
|
112 1 1 0 0 -1 7 -8 # i >= a - 7b + 8
|
|
|
113 1 -1 0 0 3 13 20 # i <= 3a + 13b + 20
|
|
|
114 1 0 1 0 0 0 -2 # j >= 2
|
|
|
115 1 2 -1 0 0 0 5 # j <= 2i + 5
|
|
|
116 1 0 0 1 0 0 0 # k >= 0
|
|
|
117 1 0 0 -1 0 0 5 # k <= 5
|
|
|
118
|
|
|
119 The number of loop iterators may change and is not connected to the
|
|
|
120 number of loops, that surrounded this bb in the gimple code. */
|
|
|
121 CloogMatrix *domain;
|
|
|
122
|
|
|
123 /* Lists containing the restrictions of the conditional statements
|
|
|
124 dominating this bb. This bb can only be executed, if all conditions
|
|
|
125 are true.
|
|
|
126
|
|
|
127 Example:
|
|
|
128
|
|
|
129 for (i = 0; i <= 20; i++)
|
|
|
130 {
|
|
|
131 A
|
|
|
132
|
|
|
133 if (2i <= 8)
|
|
|
134 B
|
|
|
135 }
|
|
|
136
|
|
|
137 So for B there is an additional condition (2i <= 8).
|
|
|
138
|
|
|
139 TODO: Add these restrictions to the domain matrix.
|
|
|
140
|
|
|
141 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
|
|
|
142 corresponding element in CONDITION_CASES is not NULL_TREE. For a
|
|
|
143 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
|
|
|
144 CASE_LABEL_EXPR. */
|
|
|
145 VEC (gimple, heap) *conditions;
|
|
|
146 VEC (gimple, heap) *condition_cases;
|
|
|
147
|
|
|
148 /* LOOPS contains for every column in the graphite domain the corresponding
|
|
|
149 gimple loop. If there exists no corresponding gimple loop LOOPS contains
|
|
|
150 NULL.
|
|
|
151
|
|
|
152 Example:
|
|
|
153
|
|
|
154 Original code:
|
|
|
155
|
|
|
156 for (i = 0; i <= 20; i++)
|
|
|
157 for (j = 5; j <= 10; j++)
|
|
|
158 A
|
|
|
159
|
|
|
160 Original domain:
|
|
|
161
|
|
|
162 (I)eq i j 1
|
|
|
163 1 1 0 0 # i >= 0
|
|
|
164 1 -1 0 20 # i <= 20
|
|
|
165 1 0 1 0 # j >= 0
|
|
|
166 1 0 -1 10 # j <= 10
|
|
|
167
|
|
|
168 Original loops vector:
|
|
|
169 0 1
|
|
|
170 Loop i Loop j
|
|
|
171
|
|
|
172 After some changes (Exchange i and j, strip-mine i):
|
|
|
173
|
|
|
174 Domain:
|
|
|
175
|
|
|
176 (I)eq j ii i k 1
|
|
|
177 1 0 0 1 0 0 # i >= 0
|
|
|
178 1 0 0 -1 0 20 # i <= 20
|
|
|
179 1 1 0 0 0 0 # j >= 0
|
|
|
180 1 -1 0 0 0 10 # j <= 10
|
|
|
181 1 0 -1 1 0 0 # ii <= i
|
|
|
182 1 0 1 -1 0 1 # ii + 1 >= i
|
|
|
183 1 0 -1 0 2 0 # ii <= 2k
|
|
|
184 1 0 1 0 -2 0 # ii >= 2k
|
|
|
185
|
|
|
186 Iterator vector:
|
|
|
187 0 1 2 3
|
|
|
188 Loop j NULL Loop i NULL
|
|
|
189
|
|
|
190 Means the original loop i is now at column two of the domain and
|
|
|
191 loop j in the original loop nest is now at column 0. Column 1 and
|
|
|
192 3 are emtpy. */
|
|
|
193 VEC (loop_p, heap) *loops;
|
|
|
194
|
|
|
195 lambda_vector compressed_alpha_matrix;
|
|
|
196 CloogMatrix *dynamic_schedule;
|
|
|
197 VEC (data_reference_p, heap) *data_refs;
|
|
|
198 htab_t cloog_iv_types;
|
|
|
199 } *gbb_p;
|
|
|
200
|
|
|
201 #define GBB_BB(GBB) GBB->bb
|
|
|
202 #define GBB_SCOP(GBB) GBB->scop
|
|
|
203 #define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
|
|
|
204 #define GBB_DATA_REFS(GBB) GBB->data_refs
|
|
|
205 #define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
|
|
|
206 #define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
|
|
|
207 #define GBB_DOMAIN(GBB) GBB->domain
|
|
|
208 #define GBB_CONDITIONS(GBB) GBB->conditions
|
|
|
209 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
|
|
|
210 #define GBB_LOOPS(GBB) GBB->loops
|
|
|
211 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
|
|
|
212
|
|
|
213 /* Return the loop that contains the basic block GBB. */
|
|
|
214
|
|
|
215 static inline struct loop *
|
|
|
216 gbb_loop (struct graphite_bb *gbb)
|
|
|
217 {
|
|
|
218 return GBB_BB (gbb)->loop_father;
|
|
|
219 }
|
|
|
220
|
|
|
221 int nb_loops_around_gb (graphite_bb_p);
|
|
|
222
|
|
|
223 /* Calculate the number of loops around GB in the current SCOP. Only
|
|
|
224 works if GBB_DOMAIN is built. */
|
|
|
225
|
|
|
226 static inline int
|
|
|
227 gbb_nb_loops (const struct graphite_bb *gb)
|
|
|
228 {
|
|
|
229 scop_p scop = GBB_SCOP (gb);
|
|
|
230
|
|
|
231 if (GBB_DOMAIN (gb) == NULL)
|
|
|
232 return 0;
|
|
|
233
|
|
|
234 return GBB_DOMAIN (gb)->NbColumns - scop_nb_params (scop) - 2;
|
|
|
235 }
|
|
|
236
|
|
|
237 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
|
|
|
238 If there is no corresponding gimple loop, we return NULL. */
|
|
|
239
|
|
|
240 static inline loop_p
|
|
|
241 gbb_loop_at_index (graphite_bb_p gb, int index)
|
|
|
242 {
|
|
|
243 return VEC_index (loop_p, GBB_LOOPS (gb), index);
|
|
|
244 }
|
|
|
245
|
|
|
246 /* Returns the index of LOOP in the loop nest around GB. */
|
|
|
247
|
|
|
248 static inline int
|
|
|
249 gbb_loop_index (graphite_bb_p gb, loop_p loop)
|
|
|
250 {
|
|
|
251 int i;
|
|
|
252 loop_p l;
|
|
|
253
|
|
|
254 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, l); i++)
|
|
|
255 if (loop == l)
|
|
|
256 return i;
|
|
|
257
|
|
|
258 gcc_unreachable();
|
|
|
259 }
|
|
|
260
|
|
|
261 struct loop_to_cloog_loop_str
|
|
|
262 {
|
|
|
263 unsigned int loop_num;
|
|
|
264 unsigned int loop_position; /* The column that represents this loop. */
|
|
|
265 CloogLoop *cloog_loop;
|
|
|
266 };
|
|
|
267
|
|
|
268 typedef struct name_tree
|
|
|
269 {
|
|
|
270 tree t;
|
|
|
271 const char *name;
|
|
|
272 struct loop *loop;
|
|
|
273 } *name_tree;
|
|
|
274
|
|
|
275 DEF_VEC_P(name_tree);
|
|
|
276 DEF_VEC_ALLOC_P (name_tree, heap);
|
|
|
277
|
|
|
278 /* A Single Entry, Single Exit region is a part of the CFG delimited
|
|
|
279 by two edges. */
|
|
|
280 typedef struct sese
|
|
|
281 {
|
|
|
282 /* Single ENTRY and single EXIT from the SESE region. */
|
|
|
283 edge entry, exit;
|
|
|
284
|
|
|
285 /* REGION_BASIC_BLOCKS contains the set of all the basic blocks
|
|
|
286 belonging to the SESE region. */
|
|
|
287 struct pointer_set_t *region_basic_blocks;
|
|
|
288
|
|
|
289 /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the
|
|
|
290 SSA_NAME is defined inside and used outside the SESE region. */
|
|
|
291 bitmap liveout;
|
|
|
292
|
|
|
293 /* The overall number of SSA_NAME versions used to index LIVEIN. */
|
|
|
294 int num_ver;
|
|
|
295
|
|
|
296 /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains
|
|
|
297 the set of basic blocks indices that contain a use of VER. */
|
|
|
298 bitmap *livein;
|
|
|
299 } *sese;
|
|
|
300
|
|
|
301 #define SESE_ENTRY(S) (S->entry)
|
|
|
302 #define SESE_EXIT(S) (S->exit)
|
|
|
303 #define SESE_REGION_BBS(S) (S->region_basic_blocks)
|
|
|
304 #define SESE_LIVEOUT(S) (S->liveout)
|
|
|
305 #define SESE_LIVEIN(S) (S->livein)
|
|
|
306 #define SESE_LIVEIN_VER(S, I) (S->livein[I])
|
|
|
307 #define SESE_NUM_VER(S) (S->num_ver)
|
|
|
308
|
|
|
309 extern sese new_sese (edge, edge);
|
|
|
310 extern void free_sese (sese);
|
|
|
311 extern void sese_build_livein_liveouts (sese);
|
|
|
312
|
|
|
313 /* A SCOP is a Static Control Part of the program, simple enough to be
|
|
|
314 represented in polyhedral form. */
|
|
|
315 struct scop
|
|
|
316 {
|
|
|
317 /* A SCOP is defined as a SESE region. */
|
|
|
318 sese region;
|
|
|
319
|
|
|
320 /* All the basic blocks in this scop that contain memory references
|
|
|
321 and that will be represented as statements in the polyhedral
|
|
|
322 representation. */
|
|
|
323 VEC (graphite_bb_p, heap) *bbs;
|
|
|
324
|
|
|
325 lambda_vector static_schedule;
|
|
|
326
|
|
|
327 /* Parameters used within the SCOP. */
|
|
|
328 VEC (name_tree, heap) *params;
|
|
|
329
|
|
|
330 /* A collection of old induction variables*/
|
|
|
331 VEC (name_tree, heap) *old_ivs;
|
|
|
332
|
|
|
333 /* Loops completely contained in the SCOP. */
|
|
|
334 bitmap loops;
|
|
|
335 VEC (loop_p, heap) *loop_nest;
|
|
|
336
|
|
|
337 /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
|
|
|
338 htab_t loop2cloog_loop;
|
|
|
339
|
|
|
340 /* Cloog representation of this scop. */
|
|
|
341 CloogProgram *program;
|
|
|
342
|
|
|
343 /* Are we allowed to add more params? This is for debugging purpose. We
|
|
|
344 can only add new params before generating the bb domains, otherwise they
|
|
|
345 become invalid. */
|
|
|
346 bool add_params;
|
|
|
347
|
|
|
348 /* LIVEOUT_RENAMES registers the rename mapping that has to be
|
|
|
349 applied after code generation. */
|
|
|
350 htab_t liveout_renames;
|
|
|
351 };
|
|
|
352
|
|
|
353 #define SCOP_BBS(S) S->bbs
|
|
|
354 #define SCOP_REGION(S) S->region
|
|
|
355 /* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
|
|
|
356 post-dominates all the bbs of the scop. SCOP_EXIT potentially
|
|
|
357 contains non affine data accesses, side effect statements or
|
|
|
358 difficult constructs, and thus is not considered part of the scop,
|
|
|
359 but just a boundary. SCOP_ENTRY is considered part of the scop. */
|
|
|
360 #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
|
|
|
361 #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
|
|
|
362 #define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
|
|
|
363 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
|
|
|
364 #define SCOP_LOOPS(S) S->loops
|
|
|
365 #define SCOP_LOOP_NEST(S) S->loop_nest
|
|
|
366 #define SCOP_ADD_PARAMS(S) S->add_params
|
|
|
367 #define SCOP_PARAMS(S) S->params
|
|
|
368 #define SCOP_OLDIVS(S) S->old_ivs
|
|
|
369 #define SCOP_PROG(S) S->program
|
|
|
370 #define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
|
|
|
371 #define SCOP_LOOPS_MAPPING(S) S->loops_mapping
|
|
|
372 #define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
|
|
|
373
|
|
|
374 extern void debug_scop (scop_p, int);
|
|
|
375 extern void debug_scops (int);
|
|
|
376 extern void print_graphite_bb (FILE *, graphite_bb_p, int, int);
|
|
|
377 extern void debug_gbb (graphite_bb_p, int);
|
|
|
378 extern void dot_scop (scop_p);
|
|
|
379 extern void dot_all_scops (void);
|
|
|
380 extern void debug_clast_stmt (struct clast_stmt *);
|
|
|
381 extern void debug_rename_map (htab_t);
|
|
|
382 extern void debug_ivtype_map (htab_t);
|
|
|
383 extern void debug_loop_vec (graphite_bb_p);
|
|
|
384 extern void debug_oldivs (scop_p);
|
|
|
385
|
|
|
386 /* Describes the type of an iv stack entry. */
|
|
|
387 typedef enum {
|
|
|
388 iv_stack_entry_unknown = 0,
|
|
|
389 iv_stack_entry_iv,
|
|
|
390 iv_stack_entry_const
|
|
|
391 } iv_stack_entry_kind;
|
|
|
392
|
|
|
393 /* Data contained in an iv stack entry. */
|
|
|
394 typedef union iv_stack_entry_data_union
|
|
|
395 {
|
|
|
396 name_tree iv;
|
|
|
397 tree constant;
|
|
|
398 } iv_stack_entry_data;
|
|
|
399
|
|
|
400 /* Datatype for loop iv stack entry. */
|
|
|
401 typedef struct iv_stack_entry_struct
|
|
|
402 {
|
|
|
403 iv_stack_entry_kind kind;
|
|
|
404 iv_stack_entry_data data;
|
|
|
405 } iv_stack_entry;
|
|
|
406
|
|
|
407 typedef iv_stack_entry *iv_stack_entry_p;
|
|
|
408
|
|
|
409 DEF_VEC_P(iv_stack_entry_p);
|
|
|
410 DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
|
|
|
411
|
|
|
412 typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
|
|
|
413 extern void debug_loop_iv_stack (loop_iv_stack);
|
|
|
414
|
|
|
415 /* Return the old induction variable of the LOOP that is in normal
|
|
|
416 form in SCOP. */
|
|
|
417
|
|
|
418 static inline tree
|
|
|
419 oldiv_for_loop (scop_p scop, loop_p loop)
|
|
|
420 {
|
|
|
421 int i;
|
|
|
422 name_tree iv;
|
|
|
423
|
|
|
424 if (!loop)
|
|
|
425 return NULL_TREE;
|
|
|
426
|
|
|
427 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
|
|
|
428 if (iv->loop == loop)
|
|
|
429 return iv->t;
|
|
|
430
|
|
|
431 return NULL_TREE;
|
|
|
432 }
|
|
|
433
|
|
|
434 /* Return the number of gimple loops contained in SCOP. */
|
|
|
435
|
|
|
436 static inline int
|
|
|
437 scop_nb_loops (scop_p scop)
|
|
|
438 {
|
|
|
439 return VEC_length (loop_p, SCOP_LOOP_NEST (scop));
|
|
|
440 }
|
|
|
441
|
|
|
442 /* Returns the number of parameters for SCOP. */
|
|
|
443
|
|
|
444 static inline unsigned
|
|
|
445 scop_nb_params (scop_p scop)
|
|
|
446 {
|
|
|
447 return VEC_length (name_tree, SCOP_PARAMS (scop));
|
|
|
448 }
|
|
|
449
|
|
|
450 /* Return the dimension of the domains for SCOP. */
|
|
|
451
|
|
|
452 static inline int
|
|
|
453 scop_dim_domain (scop_p scop)
|
|
|
454 {
|
|
|
455 return scop_nb_loops (scop) + scop_nb_params (scop) + 1;
|
|
|
456 }
|
|
|
457
|
|
|
458 /* Return the dimension of the domains for GB. */
|
|
|
459
|
|
|
460 static inline int
|
|
|
461 gbb_dim_domain (graphite_bb_p gb)
|
|
|
462 {
|
|
|
463 return scop_dim_domain (GBB_SCOP (gb));
|
|
|
464 }
|
|
|
465
|
|
|
466 /* Returns the dimensionality of a loop iteration domain for a given
|
|
|
467 loop, identified by LOOP_NUM, with respect to SCOP. */
|
|
|
468
|
|
|
469 static inline int
|
|
|
470 loop_domain_dim (unsigned int loop_num, scop_p scop)
|
|
|
471 {
|
|
|
472 struct loop_to_cloog_loop_str tmp, *slot;
|
|
|
473 htab_t tab = SCOP_LOOP2CLOOG_LOOP (scop);
|
|
|
474
|
|
|
475 tmp.loop_num = loop_num;
|
|
|
476 slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp);
|
|
|
477
|
|
|
478 /* The loop containing the entry of the scop is not always part of
|
|
|
479 the SCoP, and it is not registered in SCOP_LOOP2CLOOG_LOOP. */
|
|
|
480 if (!slot)
|
|
|
481 return scop_nb_params (scop) + 2;
|
|
|
482
|
|
|
483 return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
|
|
|
484 }
|
|
|
485
|
|
|
486 /* Returns the dimensionality of a loop iteration vector in a loop
|
|
|
487 iteration domain for a given loop (identified by LOOP_NUM) with
|
|
|
488 respect to SCOP. */
|
|
|
489
|
|
|
490 static inline int
|
|
|
491 loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
|
|
|
492 {
|
|
|
493 return loop_domain_dim (loop_num, scop) - 2 - scop_nb_params (scop);
|
|
|
494 }
|
|
|
495
|
|
|
496 /* Checks, if SCOP contains LOOP. */
|
|
|
497
|
|
|
498 static inline bool
|
|
|
499 scop_contains_loop (scop_p scop, struct loop *loop)
|
|
|
500 {
|
|
|
501 return bitmap_bit_p (SCOP_LOOPS (scop), loop->num);
|
|
|
502 }
|
|
|
503
|
|
|
504 /* Returns the index of LOOP in the domain matrix for the SCOP. */
|
|
|
505
|
|
|
506 static inline int
|
|
|
507 scop_loop_index (scop_p scop, struct loop *loop)
|
|
|
508 {
|
|
|
509 unsigned i;
|
|
|
510 struct loop *l;
|
|
|
511
|
|
|
512 gcc_assert (scop_contains_loop (scop, loop));
|
|
|
513
|
|
|
514 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
|
|
|
515 if (l == loop)
|
|
|
516 return i;
|
|
|
517
|
|
|
518 gcc_unreachable();
|
|
|
519 }
|
|
|
520
|
|
|
521 /* Return the index of innermost loop that contains the basic block
|
|
|
522 GBB. */
|
|
|
523
|
|
|
524 static inline int
|
|
|
525 gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb)
|
|
|
526 {
|
|
|
527 return scop_loop_index(scop, gbb_loop (gb));
|
|
|
528 }
|
|
|
529
|
|
|
530 /* Return the outermost loop that contains the loop LOOP. The outer
|
|
|
531 loops are searched until a sibling for the outer loop is found. */
|
|
|
532
|
|
|
533 static struct loop *
|
|
|
534 outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer)
|
|
|
535 {
|
|
|
536 return (!scop_contains_loop (scop, loop)) ? current_outer :
|
|
|
537 (loop->next != NULL) ? loop :
|
|
|
538 outer_most_loop_1 (scop, loop_outer (loop), loop);
|
|
|
539 }
|
|
|
540
|
|
|
541 /* Return the outermost loop that contains the loop LOOP. */
|
|
|
542
|
|
|
543 static struct loop *
|
|
|
544 outer_most_loop (scop_p scop, struct loop *loop)
|
|
|
545 {
|
|
|
546 return outer_most_loop_1 (scop, loop, NULL);
|
|
|
547 }
|
|
|
548
|
|
|
549 /* Return the index of the outermost loop that contains the basic
|
|
|
550 block BB. */
|
|
|
551
|
|
|
552 static inline int
|
|
|
553 gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb)
|
|
|
554 {
|
|
|
555 return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb)));
|
|
|
556 }
|
|
|
557
|
|
|
558 /* Return the loop depth of LOOP in SCOP. */
|
|
|
559
|
|
|
560 static inline unsigned int
|
|
|
561 scop_gimple_loop_depth (scop_p scop, loop_p loop)
|
|
|
562 {
|
|
|
563 unsigned int depth = 0;
|
|
|
564
|
|
|
565 loop = loop_outer (loop);
|
|
|
566
|
|
|
567 while (scop_contains_loop (scop, loop))
|
|
|
568 {
|
|
|
569 depth++;
|
|
|
570 loop = loop_outer (loop);
|
|
|
571 }
|
|
|
572
|
|
|
573 return depth;
|
|
|
574 }
|
|
|
575
|
|
|
576 #endif /* GCC_GRAPHITE_H */
|
