Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-live.h @ 89:3356a4c26abc
modify comment out :c-parser.c
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 20 Dec 2011 19:03:56 +0900 |
parents | f6334be47118 |
children | 04ced10e8804 |
rev | line source |
---|---|
0 | 1 /* Routines for liveness in SSA trees. |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Free Software Foundation, Inc. |
0 | 4 Contributed by Andrew MacLeod <amacleod@redhat.com> |
5 | |
6 This file is part of GCC. | |
7 | |
8 GCC is free software; you can redistribute it and/or modify | |
9 it under the terms of the GNU General Public License as published by | |
10 the Free Software Foundation; either version 3, or (at your option) | |
11 any later version. | |
12 | |
13 GCC is distributed in the hope that it will be useful, | |
14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 GNU General Public License for more details. | |
17 | |
18 You should have received a copy of the GNU General Public License | |
19 along with GCC; see the file COPYING3. If not see | |
20 <http://www.gnu.org/licenses/>. */ | |
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 | |
30 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
31 /* Used to create the variable mapping when we go out of SSA form. |
0 | 32 |
33 Mapping from an ssa_name to a partition number is maintained, as well as | |
34 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
|
35 by a non-ssa_name variable. This allows ssa_names and their partition to |
0 | 36 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
|
37 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
|
38 final stage of going of of ssa. |
0 | 39 |
40 Non-ssa_names maintain their partition index in the variable annotation. | |
41 | |
42 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
|
43 partitions. This allows the coalescer to decide what partitions are |
0 | 44 interesting to it, and only work with those partitions. Whenever the view |
45 is changed, the partition numbers change, but none of the partition groupings | |
46 change. (ie, it is truly a view since it doesn't change anything) | |
47 | |
48 The final component of the data structure is the basevar map. This provides | |
49 a list of all the different base variables which occur in a partition view, | |
50 and a unique index for each one. Routines are provided to quickly produce | |
51 the base variable of a partition. | |
52 | |
53 Note that members of a partition MUST all have the same base variable. */ | |
54 | |
55 typedef struct _var_map | |
56 { | |
57 /* The partition manager of all variables. */ | |
58 partition var_partition; | |
59 | |
60 /* Vector for managing partitions views. */ | |
61 int *partition_to_view; | |
62 int *view_to_partition; | |
63 | |
64 /* Current number of partitions in var_map based on the current view. */ | |
65 unsigned int num_partitions; | |
66 | |
67 /* Original full partition size. */ | |
68 unsigned int partition_size; | |
69 | |
70 /* Number of base variables in the base var list. */ | |
71 int num_basevars; | |
72 | |
73 /* Map of partitions numbers to base variable table indexes. */ | |
74 int *partition_to_base_index; | |
75 | |
76 /* Table of base variable's. */ | |
77 VEC (tree, heap) *basevars; | |
78 } *var_map; | |
79 | |
80 | |
81 /* Index to the basevar table of a non ssa-name variable. */ | |
82 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index) | |
83 | |
84 | |
85 /* Value used to represent no partition number. */ | |
86 #define NO_PARTITION -1 | |
87 | |
88 extern var_map init_var_map (int); | |
89 extern void delete_var_map (var_map); | |
90 extern void dump_var_map (FILE *, var_map); | |
91 extern int var_union (var_map, tree, tree); | |
92 extern void partition_view_normal (var_map, bool); | |
93 extern void partition_view_bitmap (var_map, bitmap, bool); | |
94 #ifdef ENABLE_CHECKING | |
95 extern void register_ssa_partition_check (tree ssa_var); | |
96 #endif | |
97 | |
98 | |
99 /* Return number of partitions in MAP. */ | |
100 | |
101 static inline unsigned | |
102 num_var_partitions (var_map map) | |
103 { | |
104 return map->num_partitions; | |
105 } | |
106 | |
107 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 /* Given partition index I from MAP, return the variable which represents that |
0 | 109 partition. */ |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
110 |
0 | 111 static inline tree |
112 partition_to_var (var_map map, int i) | |
113 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
114 tree name; |
0 | 115 if (map->view_to_partition) |
116 i = map->view_to_partition[i]; | |
117 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
|
118 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
|
119 return name; |
0 | 120 } |
121 | |
122 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
123 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
0 | 124 is associated with. Otherwise return NULL. */ |
125 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
126 static inline tree |
0 | 127 version_to_var (var_map map, int version) |
128 { | |
129 int part; | |
130 part = partition_find (map->var_partition, version); | |
131 if (map->partition_to_view) | |
132 part = map->partition_to_view[part]; | |
133 if (part == NO_PARTITION) | |
134 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
|
135 |
0 | 136 return partition_to_var (map, part); |
137 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
138 |
0 | 139 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
140 /* Given VAR, return the partition number in MAP which contains it. |
0 | 141 NO_PARTITION is returned if it's not in any partition. */ |
142 | |
143 static inline int | |
144 var_to_partition (var_map map, tree var) | |
145 { | |
146 int part; | |
147 | |
55
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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
175 gcc_checking_assert (partition >= 0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
176 && partition <= (int) num_var_partitions (map)); |
0 | 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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
274 gcc_checking_assert (live->global); |
0 | 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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
285 gcc_checking_assert (live->livein |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
286 && bb != ENTRY_BLOCK_PTR |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
287 && bb != EXIT_BLOCK_PTR); |
0 | 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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
299 gcc_checking_assert (live->liveout |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
300 && bb != ENTRY_BLOCK_PTR |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
301 && bb != EXIT_BLOCK_PTR); |
0 | 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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
322 gcc_checking_assert (live->livein[p1] && live->livein[p2]); |
0 | 323 bitmap_ior_into (live->livein[p1], live->livein[p2]); |
324 bitmap_zero (live->livein[p2]); | |
325 } | |
326 | |
327 | |
328 /* Mark partition P as live on entry to basic block BB in LIVE. */ | |
329 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
330 static inline void |
0 | 331 make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
332 { | |
333 bitmap_set_bit (live->livein[bb->index], p); | |
334 bitmap_set_bit (live->global, p); | |
335 } | |
336 | |
337 | |
338 /* From tree-ssa-coalesce.c */ | |
339 extern var_map coalesce_ssa_name (void); | |
340 | |
341 | |
342 /* 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
|
343 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
|
344 extern void dump_replaceable_exprs (FILE *, bitmap); |
0 | 345 |
346 | |
347 #endif /* _TREE_SSA_LIVE_H */ |