1/* Graphite polyhedral representation. 2 Copyright (C) 2009-2020 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 4 Tobias Grosser <grosser@fim.uni-passau.de>. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along 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 43typedef struct poly_dr *poly_dr_p; 44 45typedef struct poly_bb *poly_bb_p; 46 47typedef struct scop *scop_p; 48 49typedef unsigned graphite_dim_t; 50 51static 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. */ 55enum 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 64struct 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 203void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, 204 isl_map *, isl_set *); 205void debug_pdr (poly_dr_p); 206void print_pdr (FILE *, poly_dr_p); 207 208static inline bool 209pdr_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 216static inline bool 217pdr_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 224static inline bool 225pdr_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 232struct 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 276extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p); 277extern void print_pbb_domain (FILE *, poly_bb_p); 278extern void print_pbb (FILE *, poly_bb_p); 279extern void print_scop_context (FILE *, scop_p); 280extern void print_scop (FILE *, scop_p); 281extern void debug_pbb_domain (poly_bb_p); 282extern void debug_pbb (poly_bb_p); 283extern void print_pdrs (FILE *, poly_bb_p); 284extern void debug_pdrs (poly_bb_p); 285extern void debug_scop_context (scop_p); 286extern void debug_scop (scop_p); 287extern void print_scop_params (FILE *, scop_p); 288extern void debug_scop_params (scop_p); 289extern void print_iteration_domain (FILE *, poly_bb_p); 290extern void print_iteration_domains (FILE *, scop_p); 291extern void debug_iteration_domain (poly_bb_p); 292extern void debug_iteration_domains (scop_p); 293extern void print_isl_set (FILE *, isl_set *); 294extern void print_isl_map (FILE *, isl_map *); 295extern void print_isl_union_map (FILE *, isl_union_map *); 296extern void print_isl_aff (FILE *, isl_aff *); 297extern void print_isl_constraint (FILE *, isl_constraint *); 298extern void print_isl_schedule (FILE *, isl_schedule *); 299extern void debug_isl_schedule (isl_schedule *); 300extern void print_isl_ast (FILE *, isl_ast_node *); 301extern void debug_isl_ast (isl_ast_node *); 302extern void debug_isl_set (isl_set *); 303extern void debug_isl_map (isl_map *); 304extern void debug_isl_union_map (isl_union_map *); 305extern void debug_isl_aff (isl_aff *); 306extern void debug_isl_constraint (isl_constraint *); 307extern void debug_gmp_value (mpz_t); 308extern void debug_scop_pbb (scop_p scop, int i); 309extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p); 310extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p); 311 312/* The basic block of the PBB. */ 313 314static inline basic_block 315pbb_bb (poly_bb_p pbb) 316{ 317 return GBB_BB (PBB_BLACK_BOX (pbb)); 318} 319 320static inline int 321pbb_index (poly_bb_p pbb) 322{ 323 return pbb_bb (pbb)->index; 324} 325 326/* The loop of the PBB. */ 327 328static inline loop_p 329pbb_loop (poly_bb_p pbb) 330{ 331 return gbb_loop (PBB_BLACK_BOX (pbb)); 332} 333 334/* The scop that contains the PDR. */ 335 336static inline scop_p 337pdr_scop (poly_dr_p pdr) 338{ 339 return PBB_SCOP (PDR_PBB (pdr)); 340} 341 342/* Set black box of PBB to BLACKBOX. */ 343 344static inline void 345pbb_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 353struct 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. */ 376struct 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 423extern scop_p new_scop (edge, edge); 424extern void free_scop (scop_p); 425extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>, 426 vec<scalar_use>, vec<tree>); 427extern bool apply_poly_transforms (scop_p); 428 429/* Set the region of SCOP to REGION. */ 430 431static inline void 432scop_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 439static inline graphite_dim_t 440scop_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 447static inline void 448scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) 449{ 450 scop->nb_params = nb_params; 451} 452 453extern void scop_get_dependences (scop_p scop); 454 455bool 456carries_deps (__isl_keep isl_union_map *schedule, 457 __isl_keep isl_union_map *deps, 458 int depth); 459 460extern bool build_poly_scop (scop_p); 461extern bool graphite_regenerate_ast_isl (scop_p); 462extern void build_scops (vec<scop_p> *); 463extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree); 464extern void dot_all_sese (FILE *, vec<sese_l> &); 465extern void dot_sese (sese_l &); 466extern void dot_cfg (); 467 468#endif 469