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 #ifndef GCC_GRAPHITE_H
22 #define GCC_GRAPHITE_H
24 #include "tree-data-ref.h"
26 typedef struct graphite_bb
*graphite_bb_p
;
27 DEF_VEC_P(graphite_bb_p
);
28 DEF_VEC_ALLOC_P (graphite_bb_p
, heap
);
31 DEF_VEC_ALLOC_P (scop_p
, heap
);
33 static inline int scop_nb_loops (scop_p scop
);
34 static inline unsigned scop_nb_params (scop_p scop
);
35 static inline bool scop_contains_loop (scop_p scop
, struct loop
*loop
);
37 typedef struct graphite_bb
42 /* The static schedule contains the textual order for every loop layer.
88 - One SCoP can never contain two bbs with the same schedule timestamp.
89 - All bbs at the same loop depth have a consecutive ordering (no gaps). */
90 lambda_vector static_schedule
;
92 /* The iteration domain of this bb. It contains this columns:
93 - In/Eq: If this line is a equation or inequation.
94 - For every loop iterator one column.
95 - One column for every parameter in this SCoP.
96 - The constant column to add integers to the (in)equations.
100 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
101 for (j = 2; j <= 2*i + 5; j++)
102 for (k = 0; k <= 5; k++)
105 Loop iterators: i, j, k
110 1 1 0 0 -1 7 -8 # i >= a - 7b + 8
111 1 -1 0 0 3 13 20 # i <= 3a + 13b + 20
112 1 0 1 0 0 0 -2 # j >= 2
113 1 2 -1 0 0 0 5 # j <= 2i + 5
114 1 0 0 1 0 0 0 # k >= 0
115 1 0 0 -1 0 0 5 # k <= 5
117 The number of loop iterators may change and is not connected to the
118 number of loops, that surrounded this bb in the gimple code. */
121 /* Lists containing the restrictions of the conditional statements
122 dominating this bb. This bb can only be executed, if all conditions
127 for (i = 0; i <= 20; i++)
135 So for B there is an additional condition (2i <= 8).
137 TODO: Add these restrictions to the domain matrix.
139 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
140 corresponding element in CONDITION_CASES is not NULL_TREE. For a
141 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
143 VEC (gimple
, heap
) *conditions
;
144 VEC (gimple
, heap
) *condition_cases
;
146 /* LOOPS contains for every column in the graphite domain the corresponding
147 gimple loop. If there exists no corresponding gimple loop LOOPS contains
154 for (i = 0; i <= 20; i++)
155 for (j = 5; j <= 10; j++)
166 Original loops vector:
170 After some changes (Exchange i and j, strip-mine i):
176 1 0 0 -1 0 20 # i <= 20
178 1 -1 0 0 0 10 # j <= 10
179 1 0 -1 1 0 0 # ii <= i
180 1 0 1 -1 0 1 # ii + 1 >= i
181 1 0 -1 0 2 0 # ii <= 2k
182 1 0 1 0 -2 0 # ii >= 2k
186 Loop j NULL Loop i NULL
188 Means the original loop i is now at column two of the domain and
189 loop j in the original loop nest is now at column 0. Column 1 and
191 VEC (loop_p
, heap
) *loops
;
193 lambda_vector compressed_alpha_matrix
;
194 CloogMatrix
*dynamic_schedule
;
195 VEC (data_reference_p
, heap
) *data_refs
;
196 htab_t cloog_iv_types
;
199 #define GBB_BB(GBB) GBB->bb
200 #define GBB_SCOP(GBB) GBB->scop
201 #define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
202 #define GBB_DATA_REFS(GBB) GBB->data_refs
203 #define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
204 #define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
205 #define GBB_DOMAIN(GBB) GBB->domain
206 #define GBB_CONDITIONS(GBB) GBB->conditions
207 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
208 #define GBB_LOOPS(GBB) GBB->loops
209 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
211 /* Return the loop that contains the basic block GBB. */
213 static inline struct loop
*
214 gbb_loop (struct graphite_bb
*gbb
)
216 return GBB_BB (gbb
)->loop_father
;
219 /* Calculate the number of loops around GB in the current SCOP. Only
220 works if GBB_DOMAIN is built. */
223 gbb_nb_loops (const struct graphite_bb
*gb
)
225 scop_p scop
= GBB_SCOP (gb
);
227 if (GBB_DOMAIN (gb
) == NULL
)
230 return GBB_DOMAIN (gb
)->NbColumns
- scop_nb_params (scop
) - 2;
233 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
234 If there is no corresponding gimple loop, we return NULL. */
237 gbb_loop_at_index (graphite_bb_p gb
, int index
)
239 return VEC_index (loop_p
, GBB_LOOPS (gb
), index
);
242 /* Returns the index of LOOP in the loop nest around GB. */
245 gbb_loop_index (graphite_bb_p gb
, loop_p loop
)
250 for (i
= 0; VEC_iterate (loop_p
, GBB_LOOPS (gb
), i
, l
); i
++)
257 struct loop_to_cloog_loop_str
259 unsigned int loop_num
;
260 unsigned int loop_position
; /* The column that represents this loop. */
261 CloogLoop
*cloog_loop
;
264 typedef struct name_tree
271 DEF_VEC_P(name_tree
);
272 DEF_VEC_ALLOC_P (name_tree
, heap
);
274 /* A Single Entry, Single Exit region is a part of the CFG delimited
278 /* Single ENTRY and single EXIT from the SESE region. */
281 /* REGION_BASIC_BLOCKS contains the set of all the basic blocks
282 belonging to the SESE region. */
283 struct pointer_set_t
*region_basic_blocks
;
285 /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the
286 SSA_NAME is defined inside and used outside the SESE region. */
289 /* The overall number of SSA_NAME versions used to index LIVEIN. */
292 /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains
293 the set of basic blocks indices that contain a use of VER. */
297 #define SESE_ENTRY(S) (S->entry)
298 #define SESE_EXIT(S) (S->exit)
299 #define SESE_REGION_BBS(S) (S->region_basic_blocks)
300 #define SESE_LIVEOUT(S) (S->liveout)
301 #define SESE_LIVEIN(S) (S->livein)
302 #define SESE_LIVEIN_VER(S, I) (S->livein[I])
303 #define SESE_NUM_VER(S) (S->num_ver)
305 extern sese
new_sese (edge
, edge
);
306 extern void free_sese (sese
);
307 extern void sese_build_livein_liveouts (sese
);
309 /* A SCOP is a Static Control Part of the program, simple enough to be
310 represented in polyhedral form. */
313 /* A SCOP is defined as a SESE region. */
316 /* All the basic blocks in this scop. They have extra information
317 attached to them, in the graphite_bb structure. */
318 VEC (graphite_bb_p
, heap
) *bbs
;
320 /* Set for a basic block index when it belongs to this SCOP. */
323 lambda_vector static_schedule
;
325 /* Parameters used within the SCOP. */
326 VEC (name_tree
, heap
) *params
;
328 /* A collection of old induction variables*/
329 VEC (name_tree
, heap
) *old_ivs
;
331 /* Loops completely contained in the SCOP. */
333 VEC (loop_p
, heap
) *loop_nest
;
335 /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
336 htab_t loop2cloog_loop
;
338 /* Cloog representation of this scop. */
339 CloogProgram
*program
;
341 /* Are we allowed to add more params? This is for debugging purpose. We
342 can only add new params before generating the bb domains, otherwise they
346 /* LIVEOUT_RENAMES registers the rename mapping that has to be
347 applied after code generation. */
348 htab_t liveout_renames
;
351 #define SCOP_BBS(S) S->bbs
352 #define SCOP_BBS_B(S) S->bbs_b
353 #define SCOP_REGION(S) S->region
354 /* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
355 post-dominates all the bbs of the scop. SCOP_EXIT potentially
356 contains non affine data accesses, side effect statements or
357 difficult constructs, and thus is not considered part of the scop,
358 but just a boundary. SCOP_ENTRY is considered part of the scop. */
359 #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
360 #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
361 #define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
362 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
363 #define SCOP_LOOPS(S) S->loops
364 #define SCOP_LOOP_NEST(S) S->loop_nest
365 #define SCOP_ADD_PARAMS(S) S->add_params
366 #define SCOP_PARAMS(S) S->params
367 #define SCOP_OLDIVS(S) S->old_ivs
368 #define SCOP_PROG(S) S->program
369 #define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
370 #define SCOP_LOOPS_MAPPING(S) S->loops_mapping
371 #define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
373 extern void debug_scop (scop_p
, int);
374 extern void debug_scops (int);
375 extern void print_graphite_bb (FILE *, graphite_bb_p
, int, int);
376 extern void debug_gbb (graphite_bb_p
, int);
377 extern void dot_scop (scop_p
);
378 extern void dot_all_scops (void);
379 extern void debug_clast_stmt (struct clast_stmt
*);
380 extern void debug_rename_map (htab_t
);
381 extern void debug_ivtype_map (htab_t
);
382 extern void debug_loop_vec (graphite_bb_p
);
383 extern void debug_oldivs (scop_p
);
384 extern void debug_value (Value
);
386 /* Describes the type of an iv stack entry. */
388 iv_stack_entry_unknown
= 0,
391 } iv_stack_entry_kind
;
393 /* Data contained in an iv stack entry. */
394 typedef union iv_stack_entry_data_union
398 } iv_stack_entry_data
;
400 /* Datatype for loop iv stack entry. */
401 typedef struct iv_stack_entry_struct
403 iv_stack_entry_kind kind
;
404 iv_stack_entry_data data
;
407 typedef iv_stack_entry
*iv_stack_entry_p
;
409 DEF_VEC_P(iv_stack_entry_p
);
410 DEF_VEC_ALLOC_P(iv_stack_entry_p
,heap
);
412 typedef VEC(iv_stack_entry_p
, heap
) **loop_iv_stack
;
413 extern void debug_loop_iv_stack (loop_iv_stack
);
415 /* Return the old induction variable of the LOOP that is in normal
419 oldiv_for_loop (scop_p scop
, loop_p loop
)
427 for (i
= 0; VEC_iterate (name_tree
, SCOP_OLDIVS (scop
), i
, iv
); i
++)
428 if (iv
->loop
== loop
)
434 /* Return the number of gimple loops contained in SCOP. */
437 scop_nb_loops (scop_p scop
)
439 return VEC_length (loop_p
, SCOP_LOOP_NEST (scop
));
442 /* Returns the number of parameters for SCOP. */
444 static inline unsigned
445 scop_nb_params (scop_p scop
)
447 return VEC_length (name_tree
, SCOP_PARAMS (scop
));
450 /* Return the dimension of the domains for SCOP. */
453 scop_dim_domain (scop_p scop
)
455 return scop_nb_loops (scop
) + scop_nb_params (scop
) + 1;
458 /* Return the dimension of the domains for GB. */
461 gbb_dim_domain (graphite_bb_p gb
)
463 return scop_dim_domain (GBB_SCOP (gb
));
466 /* Returns the dimensionality of a loop iteration domain for a given
467 loop, identified by LOOP_NUM, with respect to SCOP. */
470 loop_domain_dim (unsigned int loop_num
, scop_p scop
)
472 struct loop_to_cloog_loop_str tmp
, *slot
;
473 htab_t tab
= SCOP_LOOP2CLOOG_LOOP (scop
);
475 tmp
.loop_num
= loop_num
;
476 slot
= (struct loop_to_cloog_loop_str
*) htab_find (tab
, &tmp
);
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. */
481 return scop_nb_params (scop
) + 2;
483 return cloog_domain_dim (cloog_loop_domain (slot
->cloog_loop
)) + 2;
486 /* Returns the dimensionality of a loop iteration vector in a loop
487 iteration domain for a given loop (identified by LOOP_NUM) with
491 loop_iteration_vector_dim (unsigned int loop_num
, scop_p scop
)
493 return loop_domain_dim (loop_num
, scop
) - 2 - scop_nb_params (scop
);
496 /* Checks, if SCOP contains LOOP. */
499 scop_contains_loop (scop_p scop
, struct loop
*loop
)
501 return bitmap_bit_p (SCOP_LOOPS (scop
), loop
->num
);
504 /* Returns the index of LOOP in the domain matrix for the SCOP. */
507 scop_loop_index (scop_p scop
, struct loop
*loop
)
512 gcc_assert (scop_contains_loop (scop
, loop
));
514 for (i
= 0; VEC_iterate (loop_p
, SCOP_LOOP_NEST (scop
), i
, l
); i
++)
521 /* Return the index of innermost loop that contains the basic block
525 gbb_inner_most_loop_index (scop_p scop
, graphite_bb_p gb
)
527 return scop_loop_index(scop
, gbb_loop (gb
));
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. */
534 outer_most_loop_1 (scop_p scop
, struct loop
* loop
, struct loop
* current_outer
)
536 return (!scop_contains_loop (scop
, loop
)) ? current_outer
:
537 (loop
->next
!= NULL
) ? loop
:
538 outer_most_loop_1 (scop
, loop_outer (loop
), loop
);
541 /* Return the outermost loop that contains the loop LOOP. */
544 outer_most_loop (scop_p scop
, struct loop
*loop
)
546 return outer_most_loop_1 (scop
, loop
, NULL
);
549 /* Return the index of the outermost loop that contains the basic
553 gbb_outer_most_loop_index (scop_p scop
, graphite_bb_p gb
)
555 return scop_loop_index (scop
, outer_most_loop (scop
, gbb_loop (gb
)));
558 /* Return the loop depth of LOOP in SCOP. */
560 static inline unsigned int
561 scop_gimple_loop_depth (scop_p scop
, loop_p loop
)
563 unsigned int depth
= 0;
565 loop
= loop_outer (loop
);
567 while (scop_contains_loop (scop
, loop
))
570 loop
= loop_outer (loop
);
576 /* Static inline function prototypes. */
578 static inline unsigned scop_nb_params (scop_p scop
);
580 /* Returns true when BB is in SCOP. */
583 bb_in_scop_p (basic_block bb
, scop_p scop
)
585 return bitmap_bit_p (SCOP_BBS_B (scop
), bb
->index
);
588 /* Returns true when LOOP is in SCOP. */
591 loop_in_scop_p (struct loop
*loop
, scop_p scop
)
593 return (bb_in_scop_p (loop
->header
, scop
)
594 && bb_in_scop_p (loop
->latch
, scop
));
597 /* Calculate the number of loops around LOOP in the SCOP. */
600 nb_loops_around_loop_in_scop (struct loop
*l
, scop_p scop
)
604 for (; loop_in_scop_p (l
, scop
); d
++, l
= loop_outer (l
));
609 /* Calculate the number of loops around GB in the current SCOP. */
612 nb_loops_around_gb (graphite_bb_p gb
)
614 return nb_loops_around_loop_in_scop (gbb_loop (gb
), GBB_SCOP (gb
));
617 /* Returns the dimensionality of an enclosing loop iteration domain
618 with respect to enclosing SCoP for a given data reference REF. The
619 returned dimensionality is homogeneous (depth of loop nest + number
620 of SCoP parameters + const). */
623 ref_nb_loops (data_reference_p ref
)
625 loop_p loop
= loop_containing_stmt (DR_STMT (ref
));
626 scop_p scop
= DR_SCOP (ref
);
628 return nb_loops_around_loop_in_scop (loop
, scop
) + scop_nb_params (scop
) + 2;
631 #endif /* GCC_GRAPHITE_H */