1 /* Graphite polyhedral representation. 2 Copyright (C) 2009-2018 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 4 Tobias Grosser <grosser@fim.uni-passau.de>. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #ifndef GCC_GRAPHITE_POLY_H 23 #define GCC_GRAPHITE_POLY_H 24 25 #include "sese.h" 26 #include <isl/options.h> 27 #include <isl/ctx.h> 28 #include <isl/val.h> 29 #include <isl/set.h> 30 #include <isl/union_set.h> 31 #include <isl/map.h> 32 #include <isl/union_map.h> 33 #include <isl/aff.h> 34 #include <isl/constraint.h> 35 #include <isl/flow.h> 36 #include <isl/ilp.h> 37 #include <isl/schedule.h> 38 #include <isl/ast_build.h> 39 #include <isl/schedule_node.h> 40 #include <isl/id.h> 41 #include <isl/space.h> 42 43 typedef struct poly_dr *poly_dr_p; 44 45 typedef struct poly_bb *poly_bb_p; 46 47 typedef struct scop *scop_p; 48 49 typedef unsigned graphite_dim_t; 50 51 static inline graphite_dim_t scop_nb_params (scop_p); 52 53 /* A data reference can write or read some memory or we 54 just know it may write some memory. */ 55 enum poly_dr_type 56 { 57 PDR_READ, 58 /* PDR_MAY_READs are represented using PDR_READS. This does not 59 limit the expressiveness. */ 60 PDR_WRITE, 61 PDR_MAY_WRITE 62 }; 63 64 struct poly_dr 65 { 66 /* An identifier for this PDR. */ 67 int id; 68 69 /* The number of data refs identical to this one in the PBB. */ 70 int nb_refs; 71 72 /* A pointer to the gimple stmt containing this reference. */ 73 gimple *stmt; 74 75 /* A pointer to the PBB that contains this data reference. */ 76 poly_bb_p pbb; 77 78 enum poly_dr_type type; 79 80 /* The access polyhedron contains the polyhedral space this data 81 reference will access. 82 83 The polyhedron contains these dimensions: 84 85 - The alias set (a): 86 Every memory access is classified in at least one alias set. 87 88 - The subscripts (s_0, ..., s_n): 89 The memory is accessed using zero or more subscript dimensions. 90 91 - The iteration domain (variables and parameters) 92 93 Do not hardcode the dimensions. Use the following accessor functions: 94 - pdr_alias_set_dim 95 - pdr_subscript_dim 96 - pdr_iterator_dim 97 - pdr_parameter_dim 98 99 Example: 100 101 | int A[1335][123]; 102 | int *p = malloc (); 103 | 104 | k = ... 105 | for i 106 | { 107 | if (unknown_function ()) 108 | p = A; 109 | ... = p[?][?]; 110 | for j 111 | A[i][j+k] = m; 112 | } 113 114 The data access A[i][j+k] in alias set "5" is described like this: 115 116 | i j k a s0 s1 1 117 | 0 0 0 1 0 0 -5 = 0 118 |-1 0 0 0 1 0 0 = 0 119 | 0 -1 -1 0 0 1 0 = 0 120 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the 121 | 0 0 0 0 0 1 0 >= 0 # array size. 122 | 0 0 0 0 -1 0 1335 >= 0 123 | 0 0 0 0 0 -1 123 >= 0 124 125 The pointer "*p" in alias set "5" and "7" is described as a union of 126 polyhedron: 127 128 129 | i k a s0 1 130 | 0 0 1 0 -5 = 0 131 | 0 0 0 1 0 >= 0 132 133 "or" 134 135 | i k a s0 1 136 | 0 0 1 0 -7 = 0 137 | 0 0 0 1 0 >= 0 138 139 "*p" accesses all of the object allocated with 'malloc'. 140 141 The scalar data access "m" is represented as an array with zero subscript 142 dimensions. 143 144 | i j k a 1 145 | 0 0 0 -1 15 = 0 146 147 The difference between the graphite internal format for access data and 148 the OpenSop format is in the order of columns. 149 Instead of having: 150 151 | i j k a s0 s1 1 152 | 0 0 0 1 0 0 -5 = 0 153 |-1 0 0 0 1 0 0 = 0 154 | 0 -1 -1 0 0 1 0 = 0 155 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the 156 | 0 0 0 0 0 1 0 >= 0 # array size. 157 | 0 0 0 0 -1 0 1335 >= 0 158 | 0 0 0 0 0 -1 123 >= 0 159 160 In OpenScop we have: 161 162 | a s0 s1 i j k 1 163 | 1 0 0 0 0 0 -5 = 0 164 | 0 1 0 -1 0 0 0 = 0 165 | 0 0 1 0 -1 -1 0 = 0 166 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the 167 | 0 0 1 0 0 0 0 >= 0 # array size. 168 | 0 -1 0 0 0 0 1335 >= 0 169 | 0 0 -1 0 0 0 123 >= 0 170 171 The OpenScop access function is printed as follows: 172 173 | 1 # The number of disjunct components in a union of access functions. 174 | R C O I L P # Described bellow. 175 | a s0 s1 i j k 1 176 | 1 0 0 0 0 0 -5 = 0 177 | 0 1 0 -1 0 0 0 = 0 178 | 0 0 1 0 -1 -1 0 = 0 179 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the 180 | 0 0 1 0 0 0 0 >= 0 # array size. 181 | 0 -1 0 0 0 0 1335 >= 0 182 | 0 0 -1 0 0 0 123 >= 0 183 184 Where: 185 - R: Number of rows. 186 - C: Number of columns. 187 - O: Number of output dimensions = alias set + number of subscripts. 188 - I: Number of input dimensions (iterators). 189 - L: Number of local (existentially quantified) dimensions. 190 - P: Number of parameters. 191 192 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */ 193 isl_map *accesses; 194 isl_set *subscript_sizes; 195 }; 196 197 #define PDR_ID(PDR) (PDR->id) 198 #define PDR_NB_REFS(PDR) (PDR->nb_refs) 199 #define PDR_PBB(PDR) (PDR->pbb) 200 #define PDR_TYPE(PDR) (PDR->type) 201 #define PDR_ACCESSES(PDR) (NULL) 202 203 void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, 204 isl_map *, isl_set *); 205 void debug_pdr (poly_dr_p); 206 void print_pdr (FILE *, poly_dr_p); 207 208 static inline bool 209 pdr_read_p (poly_dr_p pdr) 210 { 211 return PDR_TYPE (pdr) == PDR_READ; 212 } 213 214 /* Returns true when PDR is a "write". */ 215 216 static inline bool 217 pdr_write_p (poly_dr_p pdr) 218 { 219 return PDR_TYPE (pdr) == PDR_WRITE; 220 } 221 222 /* Returns true when PDR is a "may write". */ 223 224 static inline bool 225 pdr_may_write_p (poly_dr_p pdr) 226 { 227 return PDR_TYPE (pdr) == PDR_MAY_WRITE; 228 } 229 230 /* POLY_BB represents a blackbox in the polyhedral model. */ 231 232 struct poly_bb 233 { 234 /* Pointer to a basic block or a statement in the compiler. */ 235 gimple_poly_bb_p black_box; 236 237 /* Pointer to the SCOP containing this PBB. */ 238 scop_p scop; 239 240 /* The iteration domain of this bb. The layout of this polyhedron 241 is I|G with I the iteration domain, G the context parameters. 242 243 Example: 244 245 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++) 246 for (j = 2; j <= 2*i + 5; j++) 247 for (k = 0; k <= 5; k++) 248 S (i,j,k) 249 250 Loop iterators: i, j, k 251 Parameters: a, b 252 253 | i >= a - 7b + 8 254 | i <= 3a + 13b + 20 255 | j >= 2 256 | j <= 2i + 5 257 | k >= 0 258 | k <= 5 259 260 The number of variables in the DOMAIN may change and is not 261 related to the number of loops in the original code. */ 262 isl_set *domain; 263 isl_set *iterators; 264 265 /* The data references we access. */ 266 vec<poly_dr_p> drs; 267 268 /* The last basic block generated for this pbb. */ 269 basic_block new_bb; 270 }; 271 272 #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box) 273 #define PBB_SCOP(PBB) (PBB->scop) 274 #define PBB_DRS(PBB) (PBB->drs) 275 276 extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p); 277 extern void print_pbb_domain (FILE *, poly_bb_p); 278 extern void print_pbb (FILE *, poly_bb_p); 279 extern void print_scop_context (FILE *, scop_p); 280 extern void print_scop (FILE *, scop_p); 281 extern void debug_pbb_domain (poly_bb_p); 282 extern void debug_pbb (poly_bb_p); 283 extern void print_pdrs (FILE *, poly_bb_p); 284 extern void debug_pdrs (poly_bb_p); 285 extern void debug_scop_context (scop_p); 286 extern void debug_scop (scop_p); 287 extern void print_scop_params (FILE *, scop_p); 288 extern void debug_scop_params (scop_p); 289 extern void print_iteration_domain (FILE *, poly_bb_p); 290 extern void print_iteration_domains (FILE *, scop_p); 291 extern void debug_iteration_domain (poly_bb_p); 292 extern void debug_iteration_domains (scop_p); 293 extern void print_isl_set (FILE *, isl_set *); 294 extern void print_isl_map (FILE *, isl_map *); 295 extern void print_isl_union_map (FILE *, isl_union_map *); 296 extern void print_isl_aff (FILE *, isl_aff *); 297 extern void print_isl_constraint (FILE *, isl_constraint *); 298 extern void print_isl_schedule (FILE *, isl_schedule *); 299 extern void debug_isl_schedule (isl_schedule *); 300 extern void print_isl_ast (FILE *, isl_ast_node *); 301 extern void debug_isl_ast (isl_ast_node *); 302 extern void debug_isl_set (isl_set *); 303 extern void debug_isl_map (isl_map *); 304 extern void debug_isl_union_map (isl_union_map *); 305 extern void debug_isl_aff (isl_aff *); 306 extern void debug_isl_constraint (isl_constraint *); 307 extern void debug_gmp_value (mpz_t); 308 extern void debug_scop_pbb (scop_p scop, int i); 309 extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p); 310 extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p); 311 312 /* The basic block of the PBB. */ 313 314 static inline basic_block 315 pbb_bb (poly_bb_p pbb) 316 { 317 return GBB_BB (PBB_BLACK_BOX (pbb)); 318 } 319 320 static inline int 321 pbb_index (poly_bb_p pbb) 322 { 323 return pbb_bb (pbb)->index; 324 } 325 326 /* The loop of the PBB. */ 327 328 static inline loop_p 329 pbb_loop (poly_bb_p pbb) 330 { 331 return gbb_loop (PBB_BLACK_BOX (pbb)); 332 } 333 334 /* The scop that contains the PDR. */ 335 336 static inline scop_p 337 pdr_scop (poly_dr_p pdr) 338 { 339 return PBB_SCOP (PDR_PBB (pdr)); 340 } 341 342 /* Set black box of PBB to BLACKBOX. */ 343 344 static inline void 345 pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box) 346 { 347 pbb->black_box = black_box; 348 } 349 350 /* A helper structure to keep track of data references, polyhedral BBs, and 351 alias sets. */ 352 353 struct dr_info 354 { 355 enum { 356 invalid_alias_set = -1 357 }; 358 /* The data reference. */ 359 data_reference_p dr; 360 361 /* The polyhedral BB containing this DR. */ 362 poly_bb_p pbb; 363 364 /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph. 365 -1 is an invalid alias set. */ 366 int alias_set; 367 368 /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */ 369 dr_info (data_reference_p dr, poly_bb_p pbb, 370 int alias_set = invalid_alias_set) 371 : dr (dr), pbb (pbb), alias_set (alias_set) {} 372 }; 373 374 /* A SCOP is a Static Control Part of the program, simple enough to be 375 represented in polyhedral form. */ 376 struct scop 377 { 378 /* A SCOP is defined as a SESE region. */ 379 sese_info_p scop_info; 380 381 /* Number of parameters in SCoP. */ 382 graphite_dim_t nb_params; 383 384 /* The maximum alias set as assigned to drs by build_alias_sets. */ 385 unsigned max_alias_set; 386 387 /* All the basic blocks in this scop that contain memory references 388 and that will be represented as statements in the polyhedral 389 representation. */ 390 vec<poly_bb_p> pbbs; 391 392 /* All the data references in this scop. */ 393 vec<dr_info> drs; 394 395 /* The context describes known restrictions concerning the parameters 396 and relations in between the parameters. 397 398 void f (int8_t a, uint_16_t b) { 399 c = 2 a + b; 400 ... 401 } 402 403 Here we can add these restrictions to the context: 404 405 -128 >= a >= 127 406 0 >= b >= 65,535 407 c = 2a + b */ 408 isl_set *param_context; 409 410 /* The context used internally by isl. */ 411 isl_ctx *isl_context; 412 413 /* SCoP original schedule. */ 414 isl_schedule *original_schedule; 415 416 /* SCoP transformed schedule. */ 417 isl_schedule *transformed_schedule; 418 419 /* The data dependence relation among the data references in this scop. */ 420 isl_union_map *dependence; 421 }; 422 423 extern scop_p new_scop (edge, edge); 424 extern void free_scop (scop_p); 425 extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>, 426 vec<scalar_use>, vec<tree>); 427 extern bool apply_poly_transforms (scop_p); 428 429 /* Set the region of SCOP to REGION. */ 430 431 static inline void 432 scop_set_region (scop_p scop, sese_info_p region) 433 { 434 scop->scop_info = region; 435 } 436 437 /* Returns the number of parameters for SCOP. */ 438 439 static inline graphite_dim_t 440 scop_nb_params (scop_p scop) 441 { 442 return scop->nb_params; 443 } 444 445 /* Set the number of params of SCOP to NB_PARAMS. */ 446 447 static inline void 448 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) 449 { 450 scop->nb_params = nb_params; 451 } 452 453 extern void scop_get_dependences (scop_p scop); 454 455 bool 456 carries_deps (__isl_keep isl_union_map *schedule, 457 __isl_keep isl_union_map *deps, 458 int depth); 459 460 extern bool build_poly_scop (scop_p); 461 extern bool graphite_regenerate_ast_isl (scop_p); 462 extern void build_scops (vec<scop_p> *); 463 extern void dot_all_sese (FILE *, vec<sese_l> &); 464 extern void dot_sese (sese_l &); 465 extern void dot_cfg (); 466 467 #endif 468