Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-live.h @ 59:5b5b9ea5b220
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 15 Feb 2010 17:22:24 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Routines for liveness in SSA trees. |
| 2 Copyright (C) 2003, 2004, 2005, 2007, 2008 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 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 | |
| 22 #ifndef _TREE_SSA_LIVE_H | |
| 23 #define _TREE_SSA_LIVE_H 1 | |
| 24 | |
| 25 #include "partition.h" | |
| 26 #include "vecprim.h" | |
| 27 | |
| 28 | |
| 29 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
30 /* Used to create the variable mapping when we go out of SSA form. |
| 0 | 31 |
| 32 Mapping from an ssa_name to a partition number is maintained, as well as | |
| 33 partition number to back to ssa_name. A partition can also be represented | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
34 by a non-ssa_name variable. This allows ssa_names and their partition to |
| 0 | 35 be coalesced with live on entry compiler variables, as well as eventually |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
36 having real compiler variables assigned to each partition as part of the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
37 final stage of going of of ssa. |
| 0 | 38 |
| 39 Non-ssa_names maintain their partition index in the variable annotation. | |
| 40 | |
| 41 This data structure also supports "views", which work on a subset of all | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
42 partitions. This allows the coalescer to decide what partitions are |
| 0 | 43 interesting to it, and only work with those partitions. Whenever the view |
| 44 is changed, the partition numbers change, but none of the partition groupings | |
| 45 change. (ie, it is truly a view since it doesn't change anything) | |
| 46 | |
| 47 The final component of the data structure is the basevar map. This provides | |
| 48 a list of all the different base variables which occur in a partition view, | |
| 49 and a unique index for each one. Routines are provided to quickly produce | |
| 50 the base variable of a partition. | |
| 51 | |
| 52 Note that members of a partition MUST all have the same base variable. */ | |
| 53 | |
| 54 typedef struct _var_map | |
| 55 { | |
| 56 /* The partition manager of all variables. */ | |
| 57 partition var_partition; | |
| 58 | |
| 59 /* Vector for managing partitions views. */ | |
| 60 int *partition_to_view; | |
| 61 int *view_to_partition; | |
| 62 | |
| 63 /* Current number of partitions in var_map based on the current view. */ | |
| 64 unsigned int num_partitions; | |
| 65 | |
| 66 /* Original full partition size. */ | |
| 67 unsigned int partition_size; | |
| 68 | |
| 69 /* Number of base variables in the base var list. */ | |
| 70 int num_basevars; | |
| 71 | |
| 72 /* Map of partitions numbers to base variable table indexes. */ | |
| 73 int *partition_to_base_index; | |
| 74 | |
| 75 /* Table of base variable's. */ | |
| 76 VEC (tree, heap) *basevars; | |
| 77 } *var_map; | |
| 78 | |
| 79 | |
| 80 /* Index to the basevar table of a non ssa-name variable. */ | |
| 81 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index) | |
| 82 | |
| 83 | |
| 84 /* Value used to represent no partition number. */ | |
| 85 #define NO_PARTITION -1 | |
| 86 | |
| 87 extern var_map init_var_map (int); | |
| 88 extern void delete_var_map (var_map); | |
| 89 extern void dump_var_map (FILE *, var_map); | |
| 90 extern int var_union (var_map, tree, tree); | |
| 91 extern void partition_view_normal (var_map, bool); | |
| 92 extern void partition_view_bitmap (var_map, bitmap, bool); | |
| 93 #ifdef ENABLE_CHECKING | |
| 94 extern void register_ssa_partition_check (tree ssa_var); | |
| 95 #endif | |
| 96 | |
| 97 | |
| 98 /* Return number of partitions in MAP. */ | |
| 99 | |
| 100 static inline unsigned | |
| 101 num_var_partitions (var_map map) | |
| 102 { | |
| 103 return map->num_partitions; | |
| 104 } | |
| 105 | |
| 106 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
107 /* Given partition index I from MAP, return the variable which represents that |
| 0 | 108 partition. */ |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 |
| 0 | 110 static inline tree |
| 111 partition_to_var (var_map map, int i) | |
| 112 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 tree name; |
| 0 | 114 if (map->view_to_partition) |
| 115 i = map->view_to_partition[i]; | |
| 116 i = partition_find (map->var_partition, i); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
117 name = ssa_name (i); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
118 return name; |
| 0 | 119 } |
| 120 | |
| 121 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
122 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
| 0 | 123 is associated with. Otherwise return NULL. */ |
| 124 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
125 static inline tree |
| 0 | 126 version_to_var (var_map map, int version) |
| 127 { | |
| 128 int part; | |
| 129 part = partition_find (map->var_partition, version); | |
| 130 if (map->partition_to_view) | |
| 131 part = map->partition_to_view[part]; | |
| 132 if (part == NO_PARTITION) | |
| 133 return NULL_TREE; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 |
| 0 | 135 return partition_to_var (map, part); |
| 136 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
137 |
| 0 | 138 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
139 /* Given VAR, return the partition number in MAP which contains it. |
| 0 | 140 NO_PARTITION is returned if it's not in any partition. */ |
| 141 | |
| 142 static inline int | |
| 143 var_to_partition (var_map map, tree var) | |
| 144 { | |
| 145 int part; | |
| 146 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
147 gcc_assert (TREE_CODE (var) == SSA_NAME); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
148 part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 if (map->partition_to_view) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
150 part = map->partition_to_view[part]; |
| 0 | 151 return part; |
| 152 } | |
| 153 | |
| 154 | |
| 155 /* Given VAR, return the variable which represents the entire partition | |
| 156 it is a member of in MAP. NULL is returned if it is not in a partition. */ | |
| 157 | |
| 158 static inline tree | |
| 159 var_to_partition_to_var (var_map map, tree var) | |
| 160 { | |
| 161 int part; | |
| 162 | |
| 163 part = var_to_partition (map, var); | |
| 164 if (part == NO_PARTITION) | |
| 165 return NULL_TREE; | |
| 166 return partition_to_var (map, part); | |
| 167 } | |
| 168 | |
| 169 | |
| 170 /* Return the index into the basevar table for PARTITION's base in MAP. */ | |
| 171 | |
| 172 static inline int | |
| 173 basevar_index (var_map map, int partition) | |
| 174 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
175 gcc_assert (partition >= 0 |
| 0 | 176 && partition <= (int) num_var_partitions (map)); |
| 177 return map->partition_to_base_index[partition]; | |
| 178 } | |
| 179 | |
| 180 | |
| 181 /* Return the number of different base variables in MAP. */ | |
| 182 | |
| 183 static inline int | |
| 184 num_basevars (var_map map) | |
| 185 { | |
| 186 return map->num_basevars; | |
| 187 } | |
| 188 | |
| 189 | |
| 190 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
191 /* This routine registers a partition for SSA_VAR with MAP. Any unregistered |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
192 partitions may be filtered out by a view later. */ |
| 0 | 193 |
| 194 static inline void | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
195 register_ssa_partition (var_map map ATTRIBUTE_UNUSED, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
196 tree ssa_var ATTRIBUTE_UNUSED) |
| 0 | 197 { |
| 198 #if defined ENABLE_CHECKING | |
| 199 register_ssa_partition_check (ssa_var); | |
| 200 #endif | |
| 201 } | |
| 202 | |
| 203 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
204 /* ---------------- live on entry/exit info ------------------------------ |
| 0 | 205 |
| 206 This structure is used to represent live range information on SSA based | |
| 207 trees. A partition map must be provided, and based on the active partitions, | |
| 208 live-on-entry information and live-on-exit information can be calculated. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 As well, partitions are marked as to whether they are global (live |
| 0 | 210 outside the basic block they are defined in). |
| 211 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 The live-on-entry information is per block. It provide a bitmap for |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
213 each block which has a bit set for each partition that is live on entry to |
| 0 | 214 that block. |
| 215 | |
| 216 The live-on-exit information is per block. It provides a bitmap for each | |
| 217 block indicating which partitions are live on exit from the block. | |
| 218 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 For the purposes of this implementation, we treat the elements of a PHI |
| 0 | 220 as follows: |
| 221 | |
| 222 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they | |
| 223 originate. They are *NOT* considered live on entry to the block | |
| 224 containing the PHI node. | |
| 225 | |
| 226 The Def of a PHI node is *not* considered live on entry to the block. | |
| 227 It is considered to be "define early" in the block. Picture it as each | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 block having a stmt (or block-preheader) before the first real stmt in |
| 0 | 229 the block which defines all the variables that are defined by PHIs. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 |
| 0 | 231 ----------------------------------------------------------------------- */ |
| 232 | |
| 233 | |
| 234 typedef struct tree_live_info_d | |
| 235 { | |
| 236 /* Var map this relates to. */ | |
| 237 var_map map; | |
| 238 | |
| 239 /* Bitmap indicating which partitions are global. */ | |
| 240 bitmap global; | |
| 241 | |
| 242 /* Bitmap of live on entry blocks for partition elements. */ | |
| 243 bitmap *livein; | |
| 244 | |
| 245 /* Number of basic blocks when live on exit calculated. */ | |
| 246 int num_blocks; | |
| 247 | |
| 248 /* Vector used when creating live ranges as a visited stack. */ | |
| 249 int *work_stack; | |
| 250 | |
| 251 /* Top of workstack. */ | |
| 252 int *stack_top; | |
| 253 | |
| 254 /* Bitmap of what variables are live on exit for a basic blocks. */ | |
| 255 bitmap *liveout; | |
| 256 } *tree_live_info_p; | |
| 257 | |
| 258 | |
| 259 extern tree_live_info_p calculate_live_ranges (var_map); | |
| 260 extern void calculate_live_on_exit (tree_live_info_p); | |
| 261 extern void delete_tree_live_info (tree_live_info_p); | |
| 262 | |
| 263 #define LIVEDUMP_ENTRY 0x01 | |
| 264 #define LIVEDUMP_EXIT 0x02 | |
| 265 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) | |
| 266 extern void dump_live_info (FILE *, tree_live_info_p, int); | |
| 267 | |
| 268 | |
| 269 /* Return TRUE if P is marked as a global in LIVE. */ | |
| 270 | |
| 271 static inline int | |
| 272 partition_is_global (tree_live_info_p live, int p) | |
| 273 { | |
| 274 gcc_assert (live->global); | |
| 275 return bitmap_bit_p (live->global, p); | |
| 276 } | |
| 277 | |
| 278 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
279 /* Return the bitmap from LIVE representing the live on entry blocks for |
| 0 | 280 partition P. */ |
| 281 | |
| 282 static inline bitmap | |
| 283 live_on_entry (tree_live_info_p live, basic_block bb) | |
| 284 { | |
| 285 gcc_assert (live->livein); | |
| 286 gcc_assert (bb != ENTRY_BLOCK_PTR); | |
| 287 gcc_assert (bb != EXIT_BLOCK_PTR); | |
| 288 | |
| 289 return live->livein[bb->index]; | |
| 290 } | |
| 291 | |
| 292 | |
| 293 /* Return the bitmap from LIVE representing the live on exit partitions from | |
| 294 block BB. */ | |
| 295 | |
| 296 static inline bitmap | |
| 297 live_on_exit (tree_live_info_p live, basic_block bb) | |
| 298 { | |
| 299 gcc_assert (live->liveout); | |
| 300 gcc_assert (bb != ENTRY_BLOCK_PTR); | |
| 301 gcc_assert (bb != EXIT_BLOCK_PTR); | |
| 302 | |
| 303 return live->liveout[bb->index]; | |
| 304 } | |
| 305 | |
| 306 | |
| 307 /* Return the partition map which the information in LIVE utilizes. */ | |
| 308 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
309 static inline var_map |
| 0 | 310 live_var_map (tree_live_info_p live) |
| 311 { | |
| 312 return live->map; | |
| 313 } | |
| 314 | |
| 315 | |
| 316 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place | |
| 317 the result into P1. Clear P2. */ | |
| 318 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
319 static inline void |
| 0 | 320 live_merge_and_clear (tree_live_info_p live, int p1, int p2) |
| 321 { | |
| 322 gcc_assert (live->livein[p1]); | |
| 323 gcc_assert (live->livein[p2]); | |
| 324 bitmap_ior_into (live->livein[p1], live->livein[p2]); | |
| 325 bitmap_zero (live->livein[p2]); | |
| 326 } | |
| 327 | |
| 328 | |
| 329 /* Mark partition P as live on entry to basic block BB in LIVE. */ | |
| 330 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
331 static inline void |
| 0 | 332 make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
| 333 { | |
| 334 bitmap_set_bit (live->livein[bb->index], p); | |
| 335 bitmap_set_bit (live->global, p); | |
| 336 } | |
| 337 | |
| 338 | |
| 339 /* From tree-ssa-coalesce.c */ | |
| 340 extern var_map coalesce_ssa_name (void); | |
| 341 | |
| 342 | |
| 343 /* From tree-ssa-ter.c */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
344 extern bitmap find_replaceable_exprs (var_map); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
345 extern void dump_replaceable_exprs (FILE *, bitmap); |
| 0 | 346 |
| 347 | |
| 348 #endif /* _TREE_SSA_LIVE_H */ |