Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-live.h @ 120:f93fa5091070
fix conv1.c
author | mir3636 |
---|---|
date | Thu, 08 Mar 2018 14:53:42 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
0 | 1 /* Routines for liveness in SSA trees. |
111 | 2 Copyright (C) 2003-2017 Free Software Foundation, Inc. |
0 | 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 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
27 /* Used to create the variable mapping when we go out of SSA form. |
0 | 28 |
29 Mapping from an ssa_name to a partition number is maintained, as well as | |
111 | 30 partition number back to ssa_name. |
0 | 31 |
32 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
|
33 partitions. This allows the coalescer to decide what partitions are |
0 | 34 interesting to it, and only work with those partitions. Whenever the view |
35 is changed, the partition numbers change, but none of the partition groupings | |
36 change. (ie, it is truly a view since it doesn't change anything) | |
37 | |
38 The final component of the data structure is the basevar map. This provides | |
39 a list of all the different base variables which occur in a partition view, | |
40 and a unique index for each one. Routines are provided to quickly produce | |
41 the base variable of a partition. | |
42 | |
43 Note that members of a partition MUST all have the same base variable. */ | |
44 | |
45 typedef struct _var_map | |
46 { | |
47 /* The partition manager of all variables. */ | |
48 partition var_partition; | |
49 | |
50 /* Vector for managing partitions views. */ | |
51 int *partition_to_view; | |
52 int *view_to_partition; | |
53 | |
54 /* Current number of partitions in var_map based on the current view. */ | |
55 unsigned int num_partitions; | |
56 | |
57 /* Original full partition size. */ | |
58 unsigned int partition_size; | |
59 | |
60 /* Number of base variables in the base var list. */ | |
61 int num_basevars; | |
62 | |
63 /* Map of partitions numbers to base variable table indexes. */ | |
64 int *partition_to_base_index; | |
65 } *var_map; | |
66 | |
67 | |
68 /* Value used to represent no partition number. */ | |
69 #define NO_PARTITION -1 | |
70 | |
71 extern var_map init_var_map (int); | |
72 extern void delete_var_map (var_map); | |
111 | 73 extern int var_union (var_map, tree, tree); |
74 extern void partition_view_normal (var_map); | |
75 extern void partition_view_bitmap (var_map, bitmap); | |
76 extern void dump_scope_blocks (FILE *, dump_flags_t); | |
77 extern void debug_scope_block (tree, dump_flags_t); | |
78 extern void debug_scope_blocks (dump_flags_t); | |
79 extern void remove_unused_locals (void); | |
0 | 80 extern void dump_var_map (FILE *, var_map); |
111 | 81 extern void debug (_var_map &ref); |
82 extern void debug (_var_map *ptr); | |
0 | 83 |
84 | |
85 /* Return number of partitions in MAP. */ | |
86 | |
87 static inline unsigned | |
88 num_var_partitions (var_map map) | |
89 { | |
90 return map->num_partitions; | |
91 } | |
92 | |
93 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
94 /* Given partition index I from MAP, return the variable which represents that |
0 | 95 partition. */ |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 |
0 | 97 static inline tree |
98 partition_to_var (var_map map, int i) | |
99 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
100 tree name; |
0 | 101 if (map->view_to_partition) |
102 i = map->view_to_partition[i]; | |
103 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
|
104 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
|
105 return name; |
0 | 106 } |
107 | |
108 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 /* Given ssa_name VERSION, if it has a partition in MAP, return the var it |
0 | 110 is associated with. Otherwise return NULL. */ |
111 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
112 static inline tree |
0 | 113 version_to_var (var_map map, int version) |
114 { | |
115 int part; | |
116 part = partition_find (map->var_partition, version); | |
117 if (map->partition_to_view) | |
118 part = map->partition_to_view[part]; | |
119 if (part == NO_PARTITION) | |
120 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
|
121 |
0 | 122 return partition_to_var (map, part); |
123 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
124 |
0 | 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 /* Given VAR, return the partition number in MAP which contains it. |
0 | 127 NO_PARTITION is returned if it's not in any partition. */ |
128 | |
129 static inline int | |
130 var_to_partition (var_map map, tree var) | |
131 { | |
132 int part; | |
133 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 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
|
135 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
|
136 part = map->partition_to_view[part]; |
0 | 137 return part; |
138 } | |
139 | |
140 | |
141 /* Given VAR, return the variable which represents the entire partition | |
142 it is a member of in MAP. NULL is returned if it is not in a partition. */ | |
143 | |
144 static inline tree | |
145 var_to_partition_to_var (var_map map, tree var) | |
146 { | |
147 int part; | |
148 | |
149 part = var_to_partition (map, var); | |
150 if (part == NO_PARTITION) | |
151 return NULL_TREE; | |
152 return partition_to_var (map, part); | |
153 } | |
154 | |
155 | |
156 /* Return the index into the basevar table for PARTITION's base in MAP. */ | |
157 | |
158 static inline int | |
159 basevar_index (var_map map, int partition) | |
160 { | |
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
|
161 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
|
162 && partition <= (int) num_var_partitions (map)); |
0 | 163 return map->partition_to_base_index[partition]; |
164 } | |
165 | |
166 | |
167 /* Return the number of different base variables in MAP. */ | |
168 | |
169 static inline int | |
170 num_basevars (var_map map) | |
171 { | |
172 return map->num_basevars; | |
173 } | |
174 | |
175 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
176 /* ---------------- live on entry/exit info ------------------------------ |
0 | 177 |
178 This structure is used to represent live range information on SSA based | |
179 trees. A partition map must be provided, and based on the active partitions, | |
180 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
|
181 As well, partitions are marked as to whether they are global (live |
0 | 182 outside the basic block they are defined in). |
183 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 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
|
185 each block which has a bit set for each partition that is live on entry to |
0 | 186 that block. |
187 | |
188 The live-on-exit information is per block. It provides a bitmap for each | |
189 block indicating which partitions are live on exit from the block. | |
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 For the purposes of this implementation, we treat the elements of a PHI |
0 | 192 as follows: |
193 | |
194 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they | |
195 originate. They are *NOT* considered live on entry to the block | |
196 containing the PHI node. | |
197 | |
198 The Def of a PHI node is *not* considered live on entry to the block. | |
199 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
|
200 block having a stmt (or block-preheader) before the first real stmt in |
0 | 201 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
|
202 |
0 | 203 ----------------------------------------------------------------------- */ |
204 | |
205 | |
206 typedef struct tree_live_info_d | |
207 { | |
208 /* Var map this relates to. */ | |
209 var_map map; | |
210 | |
211 /* Bitmap indicating which partitions are global. */ | |
212 bitmap global; | |
213 | |
111 | 214 /* Bitmaps of live on entry blocks for partition elements. */ |
215 bitmap_head *livein; | |
216 | |
217 /* Bitmaps of what variables are live on exit for a basic blocks. */ | |
218 bitmap_head *liveout; | |
0 | 219 |
220 /* Number of basic blocks when live on exit calculated. */ | |
221 int num_blocks; | |
222 | |
223 /* Vector used when creating live ranges as a visited stack. */ | |
224 int *work_stack; | |
225 | |
226 /* Top of workstack. */ | |
227 int *stack_top; | |
228 | |
111 | 229 /* Obstacks to allocate the bitmaps on. */ |
230 bitmap_obstack livein_obstack; | |
231 bitmap_obstack liveout_obstack; | |
0 | 232 } *tree_live_info_p; |
233 | |
234 | |
235 #define LIVEDUMP_ENTRY 0x01 | |
236 #define LIVEDUMP_EXIT 0x02 | |
237 #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) | |
111 | 238 extern void delete_tree_live_info (tree_live_info_p); |
239 extern tree_live_info_p calculate_live_ranges (var_map, bool); | |
240 extern void debug (tree_live_info_d &ref); | |
241 extern void debug (tree_live_info_d *ptr); | |
0 | 242 extern void dump_live_info (FILE *, tree_live_info_p, int); |
243 | |
244 | |
245 /* Return TRUE if P is marked as a global in LIVE. */ | |
246 | |
247 static inline int | |
248 partition_is_global (tree_live_info_p live, int p) | |
249 { | |
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
|
250 gcc_checking_assert (live->global); |
0 | 251 return bitmap_bit_p (live->global, p); |
252 } | |
253 | |
254 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
255 /* Return the bitmap from LIVE representing the live on entry blocks for |
0 | 256 partition P. */ |
257 | |
258 static inline bitmap | |
259 live_on_entry (tree_live_info_p live, basic_block bb) | |
260 { | |
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
|
261 gcc_checking_assert (live->livein |
111 | 262 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
263 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
0 | 264 |
111 | 265 return &live->livein[bb->index]; |
0 | 266 } |
267 | |
268 | |
269 /* Return the bitmap from LIVE representing the live on exit partitions from | |
270 block BB. */ | |
271 | |
272 static inline bitmap | |
273 live_on_exit (tree_live_info_p live, basic_block bb) | |
274 { | |
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
|
275 gcc_checking_assert (live->liveout |
111 | 276 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
277 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
0 | 278 |
111 | 279 return &live->liveout[bb->index]; |
0 | 280 } |
281 | |
282 | |
283 /* Return the partition map which the information in LIVE utilizes. */ | |
284 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
285 static inline var_map |
0 | 286 live_var_map (tree_live_info_p live) |
287 { | |
288 return live->map; | |
289 } | |
290 | |
291 | |
292 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place | |
293 the result into P1. Clear P2. */ | |
294 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
295 static inline void |
0 | 296 live_merge_and_clear (tree_live_info_p live, int p1, int p2) |
297 { | |
111 | 298 gcc_checking_assert (&live->livein[p1] && &live->livein[p2]); |
299 bitmap_ior_into (&live->livein[p1], &live->livein[p2]); | |
300 bitmap_clear (&live->livein[p2]); | |
0 | 301 } |
302 | |
303 | |
304 /* Mark partition P as live on entry to basic block BB in LIVE. */ | |
305 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
306 static inline void |
0 | 307 make_live_on_entry (tree_live_info_p live, basic_block bb , int p) |
308 { | |
111 | 309 bitmap_set_bit (&live->livein[bb->index], p); |
0 | 310 bitmap_set_bit (live->global, p); |
311 } | |
312 | |
313 #endif /* _TREE_SSA_LIVE_H */ |