gcc/graphite.h

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006, 2007, 2008, 2009  Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_GRAPHITE_H
  22 #define GCC_GRAPHITE_H
  23
  24 #include "tree-data-ref.h"
  25
  26 int ref_nb_loops (data_reference_p);
  27
  28 typedef struct graphite_bb *graphite_bb_p;
  29 DEF_VEC_P(graphite_bb_p);
  30 DEF_VEC_ALLOC_P (graphite_bb_p, heap);
  31
  32 DEF_VEC_P(scop_p);
  33 DEF_VEC_ALLOC_P (scop_p, heap);
  34
  35 static inline int scop_nb_loops (scop_p scop);
  36 static inline unsigned scop_nb_params (scop_p scop);
  37 static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
  38
  39 typedef struct graphite_bb
  40 {
  41   basic_block bb;
  42   scop_p scop;
  43
  44   /* The static schedule contains the textual order for every loop layer.
  45
  46      Example:
  47
  48      S0
  49      for (i ...)
  50        {
  51          S1
  52          for (j ...)
  53            {
  54              S2
  55              S3
  56            }
  57          S4
  58        }
  59      S5
  60      for (k ...)
  61        {
  62          S6
  63          S7
  64          for (l ...)
  65            {
  66              S8
  67            }
  68          S9
  69        }
  70      S10
  71
  72      Schedules:
  73
  74         | Depth
  75      BB | 0  1  2
  76      ------------
  77      S0 | 0
  78      S1 | 1, 0
  79      S2 | 1, 1, 0
  80      S3 | 1, 1, 1
  81      S4 | 1, 2
  82      S5 | 2
  83      S6 | 3, 0
  84      S7 | 3, 1
  85      S8 | 3, 2, 0
  86      S9 | 3, 3
  87      S10| 4
  88
  89    Normalization rules:
  90      - One SCoP can never contain two bbs with the same schedule timestamp.
  91      - All bbs at the same loop depth have a consecutive ordering (no gaps). */
  92   lambda_vector static_schedule;
  93
  94   /* The iteration domain of this bb. It contains this columns:
  95      - In/Eq: If this line is a equation or inequation.
  96      - For every loop iterator one column.
  97      - One column for every parameter in this SCoP.
  98      - The constant column to add integers to the (in)equations.
  99
 100      Example:
 101
 102      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
 103        for (j = 2; j <= 2*i + 5; j++)
 104          for (k = 0; k <= 5; k++)
 105            S (i,j,k)
 106
 107      Loop iterators: i, j, k
 108      Parameters: a, b
 109
 110      (I)eq   i   j   k   a   b   1
 111
 112      1       1   0   0  -1   7   -8    #  i >=  a -  7b +  8
 113      1      -1   0   0   3   13  20    #  i <= 3a + 13b + 20
 114      1       0   1   0   0   0   -2    #  j >= 2
 115      1       2  -1   0   0   0    5    #  j <= 2i + 5
 116      1       0   0   1   0   0    0    #  k >= 0
 117      1       0   0  -1   0   0    5    #  k <= 5
 118
 119      The number of loop iterators may change and is not connected to the
 120      number of loops, that surrounded this bb in the gimple code. */
 121    CloogMatrix *domain;
 122
 123   /* Lists containing the restrictions of the conditional statements
 124      dominating this bb.  This bb can only be executed, if all conditions
 125      are true.
 126
 127      Example:
 128
 129      for (i = 0; i <= 20; i++)
 130      {
 131        A
 132
 133        if (2i <= 8)
 134          B
 135      }
 136
 137      So for B there is an additional condition (2i <= 8).
 138
 139      TODO: Add these restrictions to the domain matrix.
 140
 141      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
 142      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
 143      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
 144      CASE_LABEL_EXPR.  */
 145   VEC (gimple, heap) *conditions;
 146   VEC (gimple, heap) *condition_cases;
 147
 148   /* LOOPS contains for every column in the graphite domain the corresponding
 149      gimple loop. If there exists no corresponding gimple loop LOOPS contains
 150      NULL.
 151
 152      Example:
 153
 154      Original code:
 155
 156      for (i = 0; i <= 20; i++)
 157        for (j = 5; j <= 10; j++)
 158          A
 159
 160      Original domain:
 161
 162      (I)eq  i  j  1
 163      1      1  0  0   # i >= 0
 164      1     -1  0  20  # i <= 20
 165      1      0  1  0   # j >= 0
 166      1      0 -1  10  # j <= 10
 167
 168      Original loops vector:
 169      0         1
 170      Loop i    Loop j
 171
 172      After some changes (Exchange i and j, strip-mine i):
 173
 174      Domain:
 175
 176      (I)eq  j  ii i  k  1
 177      1      0  0  1  0  0   # i >= 0
 178      1      0  0 -1  0  20  # i <= 20
 179      1      1  0  0  0  0   # j >= 0
 180      1     -1  0  0  0  10  # j <= 10
 181      1      0 -1  1  0  0   # ii <= i
 182      1      0  1 -1  0  1   # ii + 1 >= i
 183      1      0 -1  0  2  0   # ii <= 2k
 184      1      0  1  0 -2  0   # ii >= 2k
 185
 186      Iterator vector:
 187      0        1        2         3
 188      Loop j   NULL     Loop i    NULL
 189
 190      Means the original loop i is now at column two of the domain and
 191      loop j in the original loop nest is now at column 0.  Column 1 and
 192      3 are emtpy.  */
 193   VEC (loop_p, heap) *loops;
 194
 195   lambda_vector compressed_alpha_matrix;
 196   CloogMatrix *dynamic_schedule;
 197   VEC (data_reference_p, heap) *data_refs;
 198   htab_t cloog_iv_types;
 199 } *gbb_p;
 200
 201 #define GBB_BB(GBB) GBB->bb
 202 #define GBB_SCOP(GBB) GBB->scop
 203 #define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
 204 #define GBB_DATA_REFS(GBB) GBB->data_refs
 205 #define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
 206 #define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
 207 #define GBB_DOMAIN(GBB) GBB->domain
 208 #define GBB_CONDITIONS(GBB) GBB->conditions
 209 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
 210 #define GBB_LOOPS(GBB) GBB->loops
 211 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
 212
 213 /* Return the loop that contains the basic block GBB.  */
 214
 215 static inline struct loop *
 216 gbb_loop (struct graphite_bb *gbb)
 217 {
 218   return GBB_BB (gbb)->loop_father;
 219 }
 220
 221 int nb_loops_around_gb (graphite_bb_p);
 222
 223 /* Calculate the number of loops around GB in the current SCOP.  Only
 224    works if GBB_DOMAIN is built.  */
 225
 226 static inline int
 227 gbb_nb_loops (const struct graphite_bb *gb)
 228 {
 229   scop_p scop = GBB_SCOP (gb);
 230
 231   if (GBB_DOMAIN (gb) == NULL)
 232     return 0;
 233
 234   return GBB_DOMAIN (gb)->NbColumns - scop_nb_params (scop) - 2;
 235 }
 236
 237 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
 238    If there is no corresponding gimple loop, we return NULL.  */
 239
 240 static inline loop_p
 241 gbb_loop_at_index (graphite_bb_p gb, int index)
 242 {
 243   return VEC_index (loop_p, GBB_LOOPS (gb), index);
 244 }
 245
 246 /* Returns the index of LOOP in the loop nest around GB.  */
 247
 248 static inline int
 249 gbb_loop_index (graphite_bb_p gb, loop_p loop)
 250 {
 251   int i;
 252   loop_p l;
 253
 254   for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, l); i++)
 255     if (loop == l)
 256       return i;
 257
 258   gcc_unreachable();
 259 }
 260
 261 struct loop_to_cloog_loop_str
 262 {
 263   unsigned int loop_num;
 264   unsigned int loop_position; /* The column that represents this loop.  */
 265   CloogLoop *cloog_loop;
 266 };
 267
 268 typedef struct name_tree
 269 {
 270   tree t;
 271   const char *name;
 272   struct loop *loop;
 273 } *name_tree;
 274
 275 DEF_VEC_P(name_tree);
 276 DEF_VEC_ALLOC_P (name_tree, heap);
 277
 278 /* A Single Entry, Single Exit region is a part of the CFG delimited
 279    by two edges.  */
 280 typedef struct sese
 281 {
 282   /* Single ENTRY and single EXIT from the SESE region.  */
 283   edge entry, exit;
 284
 285   /* REGION_BASIC_BLOCKS contains the set of all the basic blocks
 286      belonging to the SESE region.  */
 287   struct pointer_set_t *region_basic_blocks;
 288
 289   /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the
 290      SSA_NAME is defined inside and used outside the SESE region.  */
 291   bitmap liveout;
 292
 293   /* The overall number of SSA_NAME versions used to index LIVEIN.  */
 294   int num_ver;
 295
 296   /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains
 297      the set of basic blocks indices that contain a use of VER.  */
 298   bitmap *livein;
 299 } *sese;
 300
 301 #define SESE_ENTRY(S) (S->entry)
 302 #define SESE_EXIT(S) (S->exit)
 303 #define SESE_REGION_BBS(S) (S->region_basic_blocks)
 304 #define SESE_LIVEOUT(S) (S->liveout)
 305 #define SESE_LIVEIN(S) (S->livein)
 306 #define SESE_LIVEIN_VER(S, I) (S->livein[I])
 307 #define SESE_NUM_VER(S) (S->num_ver)
 308
 309 extern sese new_sese (edge, edge);
 310 extern void free_sese (sese);
 311 extern void sese_build_livein_liveouts (sese);
 312
 313 /* A SCOP is a Static Control Part of the program, simple enough to be
 314    represented in polyhedral form.  */
 315 struct scop
 316 {
 317   /* A SCOP is defined as a SESE region.  */
 318   sese region;
 319
 320   /* All the basic blocks in this scop that contain memory references
 321      and that will be represented as statements in the polyhedral
 322      representation.  */
 323   VEC (graphite_bb_p, heap) *bbs;
 324
 325   lambda_vector static_schedule;
 326
 327   /* Parameters used within the SCOP.  */
 328   VEC (name_tree, heap) *params;
 329
 330   /* A collection of old induction variables*/
 331   VEC (name_tree, heap) *old_ivs;
 332
 333   /* Loops completely contained in the SCOP.  */
 334   bitmap loops;
 335   VEC (loop_p, heap) *loop_nest;
 336
 337   /* ???  It looks like a global mapping loop_id -> cloog_loop would work.  */
 338   htab_t loop2cloog_loop;
 339
 340   /* Cloog representation of this scop.  */
 341   CloogProgram *program;
 342
 343   /* Are we allowed to add more params?  This is for debugging purpose.  We
 344      can only add new params before generating the bb domains, otherwise they
 345      become invalid.  */
 346   bool add_params;
 347
 348   /* LIVEOUT_RENAMES registers the rename mapping that has to be
 349      applied after code generation.  */
 350   htab_t liveout_renames;
 351 };
 352
 353 #define SCOP_BBS(S) S->bbs
 354 #define SCOP_REGION(S) S->region
 355 /* SCOP_ENTRY bb dominates all the bbs of the scop.  SCOP_EXIT bb
 356    post-dominates all the bbs of the scop.  SCOP_EXIT potentially
 357    contains non affine data accesses, side effect statements or
 358    difficult constructs, and thus is not considered part of the scop,
 359    but just a boundary.  SCOP_ENTRY is considered part of the scop.  */
 360 #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
 361 #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
 362 #define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
 363 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
 364 #define SCOP_LOOPS(S) S->loops
 365 #define SCOP_LOOP_NEST(S) S->loop_nest
 366 #define SCOP_ADD_PARAMS(S) S->add_params
 367 #define SCOP_PARAMS(S) S->params
 368 #define SCOP_OLDIVS(S) S->old_ivs
 369 #define SCOP_PROG(S) S->program
 370 #define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
 371 #define SCOP_LOOPS_MAPPING(S) S->loops_mapping
 372 #define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
 373
 374 extern void debug_scop (scop_p, int);
 375 extern void debug_scops (int);
 376 extern void print_graphite_bb (FILE *, graphite_bb_p, int, int);
 377 extern void debug_gbb (graphite_bb_p, int);
 378 extern void dot_scop (scop_p);
 379 extern void dot_all_scops (void);
 380 extern void debug_clast_stmt (struct clast_stmt *);
 381 extern void debug_rename_map (htab_t);
 382 extern void debug_ivtype_map (htab_t);
 383 extern void debug_loop_vec (graphite_bb_p);
 384 extern void debug_oldivs (scop_p);
 385
 386 /* Describes the type of an iv stack entry.  */
 387 typedef enum {
 388   iv_stack_entry_unknown = 0,
 389   iv_stack_entry_iv,
 390   iv_stack_entry_const
 391 } iv_stack_entry_kind;
 392
 393 /* Data contained in an iv stack entry.  */
 394 typedef union iv_stack_entry_data_union
 395 {
 396   name_tree iv;
 397   tree constant;
 398 } iv_stack_entry_data;
 399
 400 /* Datatype for loop iv stack entry.  */
 401 typedef struct iv_stack_entry_struct
 402 {
 403   iv_stack_entry_kind kind;
 404   iv_stack_entry_data data;
 405 } iv_stack_entry;
 406
 407 typedef iv_stack_entry *iv_stack_entry_p;
 408
 409 DEF_VEC_P(iv_stack_entry_p);
 410 DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
 411
 412 typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
 413 extern void debug_loop_iv_stack (loop_iv_stack);
 414
 415 /* Return the old induction variable of the LOOP that is in normal
 416    form in SCOP.  */
 417
 418 static inline tree
 419 oldiv_for_loop (scop_p scop, loop_p loop)
 420 {
 421   int i;
 422   name_tree iv;
 423
 424   if (!loop)
 425     return NULL_TREE;
 426
 427   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
 428     if (iv->loop == loop)
 429       return iv->t;
 430
 431   return NULL_TREE;
 432 }
 433
 434 /* Return the number of gimple loops contained in SCOP.  */
 435
 436 static inline int
 437 scop_nb_loops (scop_p scop)
 438 {
 439   return VEC_length (loop_p, SCOP_LOOP_NEST (scop));
 440 }
 441
 442 /* Returns the number of parameters for SCOP.  */
 443
 444 static inline unsigned
 445 scop_nb_params (scop_p scop)
 446 {
 447   return VEC_length (name_tree, SCOP_PARAMS (scop));
 448 }
 449
 450 /* Return the dimension of the domains for SCOP.  */
 451
 452 static inline int
 453 scop_dim_domain (scop_p scop)
 454 {
 455   return scop_nb_loops (scop) + scop_nb_params (scop) + 1;
 456 }
 457
 458 /* Return the dimension of the domains for GB.  */
 459
 460 static inline int
 461 gbb_dim_domain (graphite_bb_p gb)
 462 {
 463   return scop_dim_domain (GBB_SCOP (gb));
 464 }
 465
 466 /* Returns the dimensionality of a loop iteration domain for a given
 467    loop, identified by LOOP_NUM, with respect to SCOP.  */
 468
 469 static inline int
 470 loop_domain_dim (unsigned int loop_num, scop_p scop)
 471 {
 472   struct loop_to_cloog_loop_str tmp, *slot;
 473   htab_t tab = SCOP_LOOP2CLOOG_LOOP (scop);
 474
 475   tmp.loop_num = loop_num;
 476   slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp);
 477
 478   /* The loop containing the entry of the scop is not always part of
 479      the SCoP, and it is not registered in SCOP_LOOP2CLOOG_LOOP.  */
 480   if (!slot)
 481     return scop_nb_params (scop) + 2;
 482
 483   return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
 484 }
 485
 486 /* Returns the dimensionality of a loop iteration vector in a loop
 487    iteration domain for a given loop (identified by LOOP_NUM) with
 488    respect to SCOP.  */
 489
 490 static inline int
 491 loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
 492 {
 493   return loop_domain_dim (loop_num, scop) - 2 - scop_nb_params (scop);
 494 }
 495
 496 /* Checks, if SCOP contains LOOP.  */
 497
 498 static inline bool
 499 scop_contains_loop (scop_p scop, struct loop *loop)
 500 {
 501   return bitmap_bit_p (SCOP_LOOPS (scop), loop->num);
 502 }
 503
 504 /* Returns the index of LOOP in the domain matrix for the SCOP.  */
 505
 506 static inline int
 507 scop_loop_index (scop_p scop, struct loop *loop)
 508 {
 509   unsigned i;
 510   struct loop *l;
 511
 512   gcc_assert (scop_contains_loop (scop, loop));
 513
 514   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
 515     if (l == loop)
 516       return i;
 517
 518   gcc_unreachable();
 519 }
 520
 521 /* Return the index of innermost loop that contains the basic block
 522    GBB.  */
 523
 524 static inline int
 525 gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb)
 526 {
 527   return scop_loop_index(scop, gbb_loop (gb));
 528 }
 529
 530 /* Return the outermost loop that contains the loop LOOP.  The outer
 531    loops are searched until a sibling for the outer loop is found.  */
 532
 533 static struct loop *
 534 outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer)
 535 {
 536   return (!scop_contains_loop (scop, loop)) ? current_outer :
 537     (loop->next != NULL) ? loop :
 538     outer_most_loop_1 (scop, loop_outer (loop), loop);
 539 }
 540
 541 /* Return the outermost loop that contains the loop LOOP.  */
 542
 543 static struct loop *
 544 outer_most_loop (scop_p scop, struct loop *loop)
 545 {
 546   return outer_most_loop_1 (scop, loop, NULL);
 547 }
 548
 549 /* Return the index of the outermost loop that contains the basic
 550    block BB.  */
 551
 552 static inline int
 553 gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb)
 554 {
 555   return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb)));
 556 }
 557
 558 /* Return the loop depth of LOOP in SCOP.  */
 559
 560 static inline unsigned int
 561 scop_gimple_loop_depth (scop_p scop, loop_p loop)
 562 {
 563   unsigned int depth = 0;
 564
 565   loop = loop_outer (loop);
 566
 567   while (scop_contains_loop (scop, loop))
 568     {
 569       depth++;
 570       loop = loop_outer (loop);
 571     }
 572
 573   return depth;
 574 }
 575
 576 #endif  /* GCC_GRAPHITE_H  */