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