gcc/tree-ssa-live.h

   1 /* Routines for liveness in SSA trees.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod  <amacleod@redhat.com>
   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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22
  23 #ifndef _TREE_SSA_LIVE_H
  24 #define _TREE_SSA_LIVE_H 1
  25
  26 #include "partition.h"
  27 #include "vecprim.h"
  28
  29 /* Used to create the variable mapping when we go out of SSA form.  */
  30 typedef struct _var_map
  31 {
  32   /* The partition of all variables.  */
  33   partition var_partition;
  34
  35   /* Vector for compacting partitions.  */
  36   int *partition_to_compact;
  37   int *compact_to_partition;
  38
  39   /* Mapping of partition numbers to vars.  */
  40   tree *partition_to_var;
  41
  42   /* Current number of partitions.  */
  43   unsigned int num_partitions;
  44
  45   /* Original partition size.  */
  46   unsigned int partition_size;
  47 } *var_map;
  48
  49 #define VAR_ANN_PARTITION(ann) (ann->partition)
  50 #define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
  51
  52 #define NO_PARTITION            -1
  53
  54 /* Flags to pass to compact_var_map  */
  55
  56 #define VARMAP_NORMAL           0
  57 #define VARMAP_NO_SINGLE_DEFS   1
  58
  59 extern var_map init_var_map (int);
  60 extern void delete_var_map (var_map);
  61 extern void dump_var_map (FILE *, var_map);
  62 extern int var_union (var_map, tree, tree);
  63 extern void change_partition_var (var_map, tree, int);
  64 extern void compact_var_map (var_map, int);
  65 #ifdef ENABLE_CHECKING
  66 extern void register_ssa_partition_check (tree ssa_var);
  67 #endif
  68
  69 static inline unsigned num_var_partitions (var_map);
  70 static inline tree var_to_partition_to_var (var_map, tree);
  71 static inline tree partition_to_var (var_map, int);
  72 static inline int var_to_partition (var_map, tree);
  73 static inline tree version_to_var (var_map, int);
  74 static inline void register_ssa_partition (var_map, tree);
  75
  76 extern var_map create_ssa_var_map (void);
  77
  78 /* Number of partitions in MAP.  */
  79
  80 static inline unsigned
  81 num_var_partitions (var_map map)
  82 {
  83   return map->num_partitions;
  84 }
  85
  86
  87 /* Given partition index I from MAP, return the variable which represents that
  88    partition.  */
  89
  90 static inline tree
  91 partition_to_var (var_map map, int i)
  92 {
  93   if (map->compact_to_partition)
  94     i = map->compact_to_partition[i];
  95   i = partition_find (map->var_partition, i);
  96   return map->partition_to_var[i];
  97 }
  98
  99
 100 /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
 101    is associated with.  Otherwise return NULL.  */
 102
 103 static inline tree version_to_var (var_map map, int version)
 104 {
 105   int part;
 106   part = partition_find (map->var_partition, version);
 107   if (map->partition_to_compact)
 108     part = map->partition_to_compact[part];
 109   if (part == NO_PARTITION)
 110     return NULL_TREE;
 111
 112   return partition_to_var (map, part);
 113 }
 114
 115
 116 /* Given VAR, return the partition number in MAP which contains it.
 117    NO_PARTITION is returned if it's not in any partition.  */
 118
 119 static inline int
 120 var_to_partition (var_map map, tree var)
 121 {
 122   var_ann_t ann;
 123   int part;
 124
 125   if (TREE_CODE (var) == SSA_NAME)
 126     {
 127       part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
 128       if (map->partition_to_compact)
 129         part = map->partition_to_compact[part];
 130     }
 131   else
 132     {
 133       ann = var_ann (var);
 134       if (ann && ann->out_of_ssa_tag)
 135         part = VAR_ANN_PARTITION (ann);
 136       else
 137         part = NO_PARTITION;
 138     }
 139   return part;
 140 }
 141
 142
 143 /* Given VAR, return the variable which represents the entire partition
 144    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
 145
 146 static inline tree
 147 var_to_partition_to_var (var_map map, tree var)
 148 {
 149   int part;
 150
 151   part = var_to_partition (map, var);
 152   if (part == NO_PARTITION)
 153     return NULL_TREE;
 154   return partition_to_var (map, part);
 155 }
 156
 157
 158 /* This routine registers a partition for SSA_VAR with MAP.  IS_USE is used
 159    to count references.  Any unregistered partitions may be compacted out
 160    later.  */
 161
 162 static inline void
 163 register_ssa_partition (var_map map, tree ssa_var)
 164 {
 165   int version;
 166
 167 #if defined ENABLE_CHECKING
 168   register_ssa_partition_check (ssa_var);
 169 #endif
 170
 171   version = SSA_NAME_VERSION (ssa_var);
 172   if (map->partition_to_var[version] == NULL_TREE)
 173     map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
 174 }
 175
 176
 177 /*  ---------------- live on entry/exit info ------------------------------
 178
 179     This structure is used to represent live range information on SSA based
 180     trees. A partition map must be provided, and based on the active partitions,
 181     live-on-entry information and live-on-exit information can be calculated.
 182     As well, partitions are marked as to whether they are global (live
 183     outside the basic block they are defined in).
 184
 185     The live-on-entry information is per block.  It provide a bitmap for
 186     each block which has a bit set for each partition that is live on entry to
 187     that block.
 188
 189     The live-on-exit information is per block.  It provides a bitmap for each
 190     block indicating which partitions are live on exit from the block.
 191
 192     For the purposes of this implementation, we treat the elements of a PHI
 193     as follows:
 194
 195        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
 196        originate. They are *NOT* considered live on entry to the block
 197        containing the PHI node.
 198
 199        The Def of a PHI node is *not* considered live on entry to the block.
 200        It is considered to be "define early" in the block. Picture it as each
 201        block having a stmt (or block-preheader) before the first real stmt in
 202        the block which defines all the variables that are defined by PHIs.
 203
 204     -----------------------------------------------------------------------  */
 205
 206
 207 typedef struct tree_live_info_d
 208 {
 209   /* Var map this relates to.  */
 210   var_map map;
 211
 212   /* Bitmap indicating which partitions are global.  */
 213   bitmap global;
 214
 215   /* Bitmap of live on entry blocks for partition elements.  */
 216   bitmap *livein;
 217
 218   /* Number of basic blocks when live on exit calculated.  */
 219   int num_blocks;
 220
 221   /* Vector used when creating live ranges as a visited stack.  */
 222   int *work_stack;
 223
 224   /* Top of workstack.  */
 225   int *stack_top;
 226
 227   /* Bitmap of what variables are live on exit for a basic blocks.  */
 228   bitmap *liveout;
 229 } *tree_live_info_p;
 230
 231
 232 extern tree_live_info_p calculate_live_ranges (var_map);
 233 extern void calculate_live_on_exit (tree_live_info_p);
 234 extern void delete_tree_live_info (tree_live_info_p);
 235
 236 #define LIVEDUMP_ENTRY  0x01
 237 #define LIVEDUMP_EXIT   0x02
 238 #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 239 extern void dump_live_info (FILE *, tree_live_info_p, int);
 240
 241 static inline int partition_is_global (tree_live_info_p, int);
 242 static inline bitmap live_on_entry (tree_live_info_p, basic_block);
 243 static inline bitmap live_on_exit (tree_live_info_p, basic_block);
 244 static inline var_map live_var_map (tree_live_info_p);
 245 static inline void live_merge_and_clear (tree_live_info_p, int, int);
 246 static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
 247
 248
 249 /*  Return TRUE if P is marked as a global in LIVE.  */
 250
 251 static inline int
 252 partition_is_global (tree_live_info_p live, int p)
 253 {
 254   gcc_assert (live->global);
 255   return bitmap_bit_p (live->global, p);
 256 }
 257
 258
 259 /* Return the bitmap from LIVE representing the live on entry blocks for
 260    partition P.  */
 261
 262 static inline bitmap
 263 live_on_entry (tree_live_info_p live, basic_block bb)
 264 {
 265   gcc_assert (live->livein);
 266   gcc_assert (bb != ENTRY_BLOCK_PTR);
 267   gcc_assert (bb != EXIT_BLOCK_PTR);
 268
 269   return live->livein[bb->index];
 270 }
 271
 272
 273 /* Return the bitmap from LIVE representing the live on exit partitions from
 274    block BB.  */
 275
 276 static inline bitmap
 277 live_on_exit (tree_live_info_p live, basic_block bb)
 278 {
 279   gcc_assert (live->liveout);
 280   gcc_assert (bb != ENTRY_BLOCK_PTR);
 281   gcc_assert (bb != EXIT_BLOCK_PTR);
 282
 283   return live->liveout[bb->index];
 284 }
 285
 286
 287 /* Return the partition map which the information in LIVE utilizes.  */
 288
 289 static inline var_map
 290 live_var_map (tree_live_info_p live)
 291 {
 292   return live->map;
 293 }
 294
 295
 296 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
 297    the result into P1.  Clear P2.  */
 298
 299 static inline void
 300 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 301 {
 302   gcc_assert (live->livein[p1]);
 303   gcc_assert (live->livein[p2]);
 304   bitmap_ior_into (live->livein[p1], live->livein[p2]);
 305   bitmap_zero (live->livein[p2]);
 306 }
 307
 308
 309 /* Mark partition P as live on entry to basic block BB in LIVE.  */
 310
 311 static inline void
 312 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 313 {
 314   bitmap_set_bit (live->livein[bb->index], p);
 315   bitmap_set_bit (live->global, p);
 316 }
 317
 318
 319 /* A tree_partition_associator (TPA)object is a base structure which allows
 320    partitions to be associated with a tree object.
 321
 322    A varray of tree elements represent each distinct tree item.
 323    A parallel int array represents the first partition number associated with
 324    the tree.
 325    This partition number is then used as in index into the next_partition
 326    array, which returns the index of the next partition which is associated
 327    with the tree. TPA_NONE indicates the end of the list.
 328    A varray paralleling the partition list 'partition_to_tree_map' is used
 329    to indicate which tree index the partition is in.  */
 330
 331 typedef struct tree_partition_associator_d
 332 {
 333   VEC(tree,heap) *trees;
 334   VEC(int,heap) *first_partition;
 335   int *next_partition;
 336   int *partition_to_tree_map;
 337   int num_trees;
 338   int uncompressed_num;
 339   var_map map;
 340 } *tpa_p;
 341
 342 /* Value returned when there are no more partitions associated with a tree.  */
 343 #define TPA_NONE                -1
 344
 345 static inline tree tpa_tree (tpa_p, int);
 346 static inline int tpa_first_partition (tpa_p, int);
 347 static inline int tpa_next_partition (tpa_p, int);
 348 static inline int tpa_num_trees (tpa_p);
 349 static inline int tpa_find_tree (tpa_p, int);
 350 static inline void tpa_decompact (tpa_p);
 351 extern void tpa_delete (tpa_p);
 352 extern void tpa_dump (FILE *, tpa_p);
 353 extern void tpa_remove_partition (tpa_p, int, int);
 354 extern int tpa_compact (tpa_p);
 355
 356
 357 /* Return the number of distinct tree nodes in TPA.  */
 358
 359 static inline int
 360 tpa_num_trees (tpa_p tpa)
 361 {
 362   return tpa->num_trees;
 363 }
 364
 365
 366 /* Return the tree node for index I in TPA.  */
 367
 368 static inline tree
 369 tpa_tree (tpa_p tpa, int i)
 370 {
 371   return VEC_index (tree, tpa->trees, i);
 372 }
 373
 374
 375 /* Return the first partition associated with tree list I in TPA.  */
 376
 377 static inline int
 378 tpa_first_partition (tpa_p tpa, int i)
 379 {
 380   return VEC_index (int, tpa->first_partition, i);
 381 }
 382
 383
 384 /* Return the next partition after partition I in TPA's list.  */
 385
 386 static inline int
 387 tpa_next_partition (tpa_p tpa, int i)
 388 {
 389   return tpa->next_partition[i];
 390 }
 391
 392
 393 /* Return the tree index from TPA whose list contains partition I.
 394    TPA_NONE is returned if I is not associated with any list.  */
 395
 396 static inline int
 397 tpa_find_tree (tpa_p tpa, int i)
 398 {
 399   int index;
 400
 401   index = tpa->partition_to_tree_map[i];
 402   /* When compressed, any index higher than the number of tree elements is
 403      a compressed element, so return TPA_NONE.  */
 404   if (index != TPA_NONE && index >= tpa_num_trees (tpa))
 405     {
 406       gcc_assert (tpa->uncompressed_num != -1);
 407       index = TPA_NONE;
 408     }
 409
 410   return index;
 411 }
 412
 413
 414 /* This function removes any compaction which was performed on TPA.  */
 415
 416 static inline void
 417 tpa_decompact(tpa_p tpa)
 418 {
 419   gcc_assert (tpa->uncompressed_num != -1);
 420   tpa->num_trees = tpa->uncompressed_num;
 421 }
 422
 423
 424 /* Once a var_map has been created and compressed, a complementary root_var
 425    object can be built.  This creates a list of all the root variables from
 426    which ssa version names are derived.  Each root variable has a list of
 427    which partitions are versions of that root.
 428
 429    This is implemented using the tree_partition_associator.
 430
 431    The tree vector is used to represent the root variable.
 432    The list of partitions represent SSA versions of the root variable.  */
 433
 434 typedef tpa_p root_var_p;
 435
 436 static inline tree root_var (root_var_p, int);
 437 static inline int root_var_first_partition (root_var_p, int);
 438 static inline int root_var_next_partition (root_var_p, int);
 439 static inline int root_var_num (root_var_p);
 440 static inline void root_var_dump (FILE *, root_var_p);
 441 static inline void root_var_remove_partition (root_var_p, int, int);
 442 static inline void root_var_delete (root_var_p);
 443 static inline int root_var_find (root_var_p, int);
 444 static inline int root_var_compact (root_var_p);
 445 static inline void root_var_decompact (tpa_p);
 446
 447 extern root_var_p root_var_init (var_map);
 448
 449 /* Value returned when there are no more partitions associated with a root
 450    variable.  */
 451 #define ROOT_VAR_NONE           TPA_NONE
 452
 453
 454 /* Return the number of distinct root variables in RV.  */
 455
 456 static inline int
 457 root_var_num (root_var_p rv)
 458 {
 459   return tpa_num_trees (rv);
 460 }
 461
 462
 463 /* Return root variable I from RV.  */
 464
 465 static inline tree
 466 root_var (root_var_p rv, int i)
 467 {
 468   return tpa_tree (rv, i);
 469 }
 470
 471
 472 /* Return the first partition in RV belonging to root variable list I.  */
 473
 474 static inline int
 475 root_var_first_partition (root_var_p rv, int i)
 476 {
 477   return tpa_first_partition (rv, i);
 478 }
 479
 480
 481 /* Return the next partition after partition I in a root list from RV.  */
 482
 483 static inline int
 484 root_var_next_partition (root_var_p rv, int i)
 485 {
 486   return tpa_next_partition (rv, i);
 487 }
 488
 489
 490 /* Send debug info for root_var list RV to file F.  */
 491
 492 static inline void
 493 root_var_dump (FILE *f, root_var_p rv)
 494 {
 495   fprintf (f, "\nRoot Var dump\n");
 496   tpa_dump (f, rv);
 497   fprintf (f, "\n");
 498 }
 499
 500
 501 /* Destroy root_var object RV.  */
 502
 503 static inline void
 504 root_var_delete (root_var_p rv)
 505 {
 506   tpa_delete (rv);
 507 }
 508
 509
 510 /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV.  */
 511
 512 static inline void
 513 root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
 514 {
 515   tpa_remove_partition (rv, root_index, partition_index);
 516 }
 517
 518
 519 /* Return the root_var list index for partition I in RV.  */
 520
 521 static inline int
 522 root_var_find (root_var_p rv, int i)
 523 {
 524   return tpa_find_tree (rv, i);
 525 }
 526
 527
 528 /* Hide single element lists in RV.  */
 529
 530 static inline int
 531 root_var_compact (root_var_p rv)
 532 {
 533   return tpa_compact (rv);
 534 }
 535
 536
 537 /* Expose the single element lists in RV.  */
 538
 539 static inline void
 540 root_var_decompact (root_var_p rv)
 541 {
 542   tpa_decompact (rv);
 543 }
 544
 545
 546 /* This set of routines implements a coalesce_list. This is an object which
 547    is used to track pairs of partitions which are desirable to coalesce
 548    together at some point.  Costs are associated with each pair, and when
 549    all desired information has been collected, the object can be used to
 550    order the pairs for processing.  */
 551
 552 /* This structure defines a pair entry.  */
 553
 554 typedef struct partition_pair
 555 {
 556   int first_partition;
 557   int second_partition;
 558   int cost;
 559 } * partition_pair_p;
 560
 561 extern unsigned int partition_pair_map_hash (const void *);
 562 extern int partition_pair_map_eq (const void *, const void *);
 563
 564 /* This structure maintains the list of coalesce pairs.  */
 565
 566 typedef struct coalesce_list_d
 567 {
 568   var_map map;
 569   htab_t list;
 570   partition_pair_p *sorted;
 571   int num_sorted;
 572   bool add_mode;
 573 } *coalesce_list_p;
 574
 575 extern coalesce_list_p create_coalesce_list (var_map);
 576 extern void add_coalesce (coalesce_list_p, int, int, int);
 577 extern int coalesce_cost (int, bool, bool);
 578 extern void sort_coalesce_list (coalesce_list_p);
 579 extern void dump_coalesce_list (FILE *, coalesce_list_p);
 580 extern void delete_coalesce_list (coalesce_list_p);
 581
 582 #define NO_BEST_COALESCE        -1
 583
 584 extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
 585                                                  coalesce_list_p);
 586 extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
 587                                   coalesce_list_p cl, FILE *);
 588
 589
 590 #endif /* _TREE_SSA_LIVE_H  */