graphite.h 13 KB

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