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