1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
5 This file is part of GCC.
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)
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.
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/>. */
21 #include "tree-data-ref.h"
23 typedef struct graphite_bb *graphite_bb_p;
24 DEF_VEC_P(graphite_bb_p);
25 DEF_VEC_ALLOC_P (graphite_bb_p, heap);
28 DEF_VEC_ALLOC_P (scop_p, heap);
30 static inline int scop_nb_loops (scop_p scop);
31 static inline unsigned scop_nb_params (scop_p scop);
32 static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
39 /* The static schedule contains the textual order for every loop layer.
85 - One SCoP can never contain two bbs with the same schedule timestamp.
86 - All bbs at the same loop depth have a consecutive ordering (no gaps). */
87 lambda_vector static_schedule;
89 /* The iteration domain of this bb. It contains this columns:
90 - In/Eq: If this line is a equation or inequation.
91 - For every loop iterator one column.
92 - One column for every parameter in this SCoP.
93 - The constant column to add integers to the (in)equations.
97 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
98 for (j = 2; j <= 2*i + 5; j++)
99 for (k = 0; k <= 5; k++)
102 Loop iterators: i, j, k
107 1 1 0 0 -1 7 -8 # i >= a - 7b + 8
108 1 -1 0 0 3 13 20 # i <= 3a + 13b + 20
109 1 0 1 0 0 0 -2 # j >= 2
110 1 2 -1 0 0 0 5 # j <= 2i + 5
111 1 0 0 1 0 0 0 # k >= 0
112 1 0 0 -1 0 0 5 # k <= 5
114 The number of loop iterators may change and is not connected to the
115 number of loops, that surrounded this bb in the gimple code. */
118 /* Lists containing the restrictions of the conditional statements
119 dominating this bb. This bb can only be executed, if all conditions
124 for (i = 0; i <= 20; i++)
132 So for B there is a additional condition (2i <= 8).
134 TODO: Add this restrictions to the domain matrix.
136 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
137 corresponding element in CONDITION_CASES is not NULL_TREE. For a
138 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
140 VEC (gimple, heap) *conditions;
141 VEC (gimple, heap) *condition_cases;
143 /* LOOPS contains for every column in the graphite domain the corresponding
144 gimple loop. If there exists no corresponding gimple loop LOOPS contains
151 for (i = 0; i <= 20; i++)
152 for (j = 5; j <= 10; j++)
163 Original loops vector:
167 After some changes (Exchange i and j, strip-mine i):
173 1 0 0 -1 0 20 # i <= 20
175 1 -1 0 0 0 10 # j <= 10
176 1 0 -1 1 0 0 # ii <= i
177 1 0 1 -1 0 1 # ii + 1 >= i
178 1 0 -1 0 2 0 # ii <= 2k
179 1 0 1 0 -2 0 # ii >= 2k
183 Loop j NULL Loop i NULL
185 Means the original loop i is now at column two of the domain and
186 loop j in the original loop nest is now at column 0. Column 1 and
188 VEC (loop_p, heap) *loops;
190 lambda_vector compressed_alpha_matrix;
191 CloogMatrix *dynamic_schedule;
192 VEC (data_reference_p, heap) *data_refs;
195 #define GBB_BB(GBB) GBB->bb
196 #define GBB_SCOP(GBB) GBB->scop
197 #define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
198 #define GBB_DATA_REFS(GBB) GBB->data_refs
199 #define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
200 #define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
201 #define GBB_DOMAIN(GBB) GBB->domain
202 #define GBB_CONDITIONS(GBB) GBB->conditions
203 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
204 #define GBB_LOOPS(GBB) GBB->loops
206 /* Return the loop that contains the basic block GBB. */
208 static inline struct loop *
209 gbb_loop (struct graphite_bb *gbb)
211 return GBB_BB (gbb)->loop_father;
214 /* Calculate the number of loops around GB in the current SCOP. Only
215 works if GBB_DOMAIN is built. */
218 gbb_nb_loops (const struct graphite_bb *gb)
220 scop_p scop = GBB_SCOP (gb);
222 if (GBB_DOMAIN (gb) == NULL)
225 return GBB_DOMAIN (gb)->NbColumns - scop_nb_params (scop) - 2;
228 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
229 If there is no corresponding gimple loop, we return NULL. */
232 gbb_loop_at_index (graphite_bb_p gb, int index)
234 return VEC_index (loop_p, GBB_LOOPS (gb), index);
237 /* Returns the corresponding loop iterator index for a gimple loop. */
240 gbb_loop_index (graphite_bb_p gb, loop_p loop)
245 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, l); i++)
252 struct loop_to_cloog_loop_str
254 unsigned int loop_num;
255 unsigned int loop_position; /* The column that represents this loop. */
256 CloogLoop *cloog_loop;
259 typedef struct name_tree
266 DEF_VEC_P(name_tree);
267 DEF_VEC_ALLOC_P (name_tree, heap);
269 /* A Single Entry, Single Exit region is a part of the CFG delimited
276 #define SESE_ENTRY(S) (S->entry)
277 #define SESE_EXIT(S) (S->exit)
279 /* A SCOP is a Static Control Part of the program, simple enough to be
280 represented in polyhedral form. */
283 /* A SCOP is defined as a SESE region. */
286 /* All the basic blocks in this scop. They have extra information
287 attached to them, in the graphite_bb structure. */
288 VEC (graphite_bb_p, heap) *bbs;
290 /* Set for a basic block index when it belongs to this SCOP. */
293 lambda_vector static_schedule;
295 /* Parameters used within the SCOP. */
296 VEC (name_tree, heap) *params;
298 /* A collection of old induction variables*/
299 VEC (name_tree, heap) *old_ivs;
301 /* Loops completely contained in the SCOP. */
303 VEC (loop_p, heap) *loop_nest;
305 /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
306 htab_t loop2cloog_loop;
308 /* CLooG representation of this SCOP. */
309 CloogProgram *program;
312 #define SCOP_BBS(S) S->bbs
313 #define SCOP_BBS_B(S) S->bbs_b
314 #define SCOP_REGION(S) S->region
315 /* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
316 post-dominates all the bbs of the scop. SCOP_EXIT potentially
317 contains non affine data accesses, side effect statements or
318 difficult constructs, and thus is not considered part of the scop,
319 but just a boundary. SCOP_ENTRY is considered part of the scop. */
320 #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
321 #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
322 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
323 #define SCOP_LOOPS(S) S->loops
324 #define SCOP_LOOP_NEST(S) S->loop_nest
325 #define SCOP_PARAMS(S) S->params
326 #define SCOP_OLDIVS(S) S->old_ivs
327 #define SCOP_PROG(S) S->program
328 #define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
329 #define SCOP_LOOPS_MAPPING(S) S->loops_mapping
331 extern void debug_scop (scop_p, int);
332 extern void debug_scops (int);
333 extern void print_graphite_bb (FILE *, graphite_bb_p, int, int);
334 extern void debug_gbb (graphite_bb_p, int);
335 extern void dot_scop (scop_p);
336 extern void dot_all_scops (void);
337 extern void debug_clast_stmt (struct clast_stmt *);
340 extern void debug_loop_vec (graphite_bb_p gb);
341 extern void debug_oldivs (scop_p);
343 /* Describes the type of an iv stack entry. */
345 iv_stack_entry_unknown = 0,
348 } iv_stack_entry_kind;
350 /* Data contained in an iv stack entry. */
351 typedef union iv_stack_entry_data_union
355 } iv_stack_entry_data;
357 /* Datatype for loop iv stack entry. */
358 typedef struct iv_stack_entry_struct
360 iv_stack_entry_kind kind;
361 iv_stack_entry_data data;
364 typedef iv_stack_entry *iv_stack_entry_p;
366 DEF_VEC_P(iv_stack_entry_p);
367 DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
369 typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
370 extern void debug_loop_iv_stack (loop_iv_stack);
373 /* Return the number of gimple loops contained in SCOP. */
376 scop_nb_loops (scop_p scop)
378 return VEC_length (loop_p, SCOP_LOOP_NEST (scop));
381 /* Returns the number of parameters for SCOP. */
383 static inline unsigned
384 scop_nb_params (scop_p scop)
386 return VEC_length (name_tree, SCOP_PARAMS (scop));
389 /* Return the dimension of the domains for SCOP. */
392 scop_dim_domain (scop_p scop)
394 return scop_nb_loops (scop) + scop_nb_params (scop) + 1;
397 /* Return the dimension of the domains for GB. */
400 gbb_dim_domain (graphite_bb_p gb)
402 return scop_dim_domain (GBB_SCOP (gb));
405 /* Returns the dimensionality of a loop iteration domain for a given
406 loop, identified by LOOP_NUM, with respect to SCOP. */
409 loop_domain_dim (unsigned int loop_num, scop_p scop)
411 struct loop_to_cloog_loop_str tmp, *slot;
412 htab_t tab = SCOP_LOOP2CLOOG_LOOP (scop);
414 tmp.loop_num = loop_num;
415 slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp);
417 /* The loop containing the entry of the scop is not always part of
418 the SCoP, and it is not registered in SCOP_LOOP2CLOOG_LOOP. */
420 return scop_nb_params (scop) + 2;
422 return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
425 /* Returns the dimensionality of an enclosing loop iteration domain
426 with respect to enclosing SCoP for a given data reference REF. */
429 ref_nb_loops (data_reference_p ref)
431 return loop_domain_dim (loop_containing_stmt (DR_STMT (ref))->num, DR_SCOP (ref));
434 /* Returns the dimensionality of a loop iteration vector in a loop
435 iteration domain for a given loop (identified by LOOP_NUM) with
439 loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
441 return loop_domain_dim (loop_num, scop) - 2 - scop_nb_params (scop);
444 /* Checks, if SCOP contains LOOP. */
447 scop_contains_loop (scop_p scop, struct loop *loop)
449 return bitmap_bit_p (SCOP_LOOPS (scop), loop->num);
452 /* Returns the index of LOOP in the domain matrix for the SCOP. */
455 scop_loop_index (scop_p scop, struct loop *loop)
460 gcc_assert (scop_contains_loop (scop, loop));
462 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
469 /* Return the index of innermost loop that contains the basic block
473 gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb)
475 return scop_loop_index(scop, gbb_loop (gb));
478 /* Return the outermost loop that contains the loop LOOP. The outer
479 loops are searched until a sibling for the outer loop is found. */
482 outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer)
484 return (!scop_contains_loop (scop, loop)) ? current_outer :
485 (loop->next != NULL) ? loop :
486 outer_most_loop_1 (scop, loop_outer (loop), loop);
489 /* Return the outermost loop that contains the loop LOOP. */
492 outer_most_loop (scop_p scop, struct loop *loop)
494 return outer_most_loop_1 (scop, loop, NULL);
497 /* Return the index of the outermost loop that contains the basic
501 gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb)
503 return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb)));
506 /* Return the loop depth of LOOP in SCOP. */
508 static inline unsigned int
509 scop_gimple_loop_depth (scop_p scop, loop_p loop)
511 unsigned int depth = 0;
513 loop = loop_outer (loop);
515 while (scop_contains_loop (scop, loop))
518 loop = loop_outer (loop);
524 /* Associate a POLYHEDRON dependence description to two data
525 references A and B. */
526 struct data_dependence_polyhedron
528 struct data_reference *a;
529 struct data_reference *b;
531 bool loop_carried; /*TODO:konrad get rid of this, make level signed */
533 CloogDomain *polyhedron;
536 #define RDGE_DDP(E) ((struct data_dependence_polyhedron*) ((E)->data))
538 typedef struct data_dependence_polyhedron *ddp_p;
541 DEF_VEC_ALLOC_P(ddp_p,heap);