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