gcc/graphite.h

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