|
0
|
1 /* Generic routines for manipulating PHIs
|
|
|
2 Copyright (C) 2003, 2005, 2007, 2008 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify
|
|
|
7 it under the terms of the GNU General Public License as published by
|
|
|
8 the Free Software Foundation; either version 3, or (at your option)
|
|
|
9 any later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful,
|
|
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
14 GNU General Public License for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "varray.h"
|
|
|
27 #include "ggc.h"
|
|
|
28 #include "basic-block.h"
|
|
|
29 #include "tree-flow.h"
|
|
|
30 #include "toplev.h"
|
|
|
31 #include "gimple.h"
|
|
|
32
|
|
|
33 /* Rewriting a function into SSA form can create a huge number of PHIs
|
|
|
34 many of which may be thrown away shortly after their creation if jumps
|
|
|
35 were threaded through PHI nodes.
|
|
|
36
|
|
|
37 While our garbage collection mechanisms will handle this situation, it
|
|
|
38 is extremely wasteful to create nodes and throw them away, especially
|
|
|
39 when the nodes can be reused.
|
|
|
40
|
|
|
41 For PR 8361, we can significantly reduce the number of nodes allocated
|
|
|
42 and thus the total amount of memory allocated by managing PHIs a
|
|
|
43 little. This additionally helps reduce the amount of work done by the
|
|
|
44 garbage collector. Similar results have been seen on a wider variety
|
|
|
45 of tests (such as the compiler itself).
|
|
|
46
|
|
|
47 Right now we maintain our free list on a per-function basis. It may
|
|
|
48 or may not make sense to maintain the free list for the duration of
|
|
|
49 a compilation unit.
|
|
|
50
|
|
|
51 We could also use a zone allocator for these objects since they have
|
|
|
52 a very well defined lifetime. If someone wants to experiment with that
|
|
|
53 this is the place to try it.
|
|
|
54
|
|
|
55 PHI nodes have different sizes, so we can't have a single list of all
|
|
|
56 the PHI nodes as it would be too expensive to walk down that list to
|
|
|
57 find a PHI of a suitable size.
|
|
|
58
|
|
|
59 Instead we have an array of lists of free PHI nodes. The array is
|
|
|
60 indexed by the number of PHI alternatives that PHI node can hold.
|
|
|
61 Except for the last array member, which holds all remaining PHI
|
|
|
62 nodes.
|
|
|
63
|
|
|
64 So to find a free PHI node, we compute its index into the free PHI
|
|
|
65 node array and see if there are any elements with an exact match.
|
|
|
66 If so, then we are done. Otherwise, we test the next larger size
|
|
|
67 up and continue until we are in the last array element.
|
|
|
68
|
|
|
69 We do not actually walk members of the last array element. While it
|
|
|
70 might allow us to pick up a few reusable PHI nodes, it could potentially
|
|
|
71 be very expensive if the program has released a bunch of large PHI nodes,
|
|
|
72 but keeps asking for even larger PHI nodes. Experiments have shown that
|
|
|
73 walking the elements of the last array entry would result in finding less
|
|
|
74 than .1% additional reusable PHI nodes.
|
|
|
75
|
|
|
76 Note that we can never have less than two PHI argument slots. Thus,
|
|
|
77 the -2 on all the calculations below. */
|
|
|
78
|
|
|
79 #define NUM_BUCKETS 10
|
|
|
80 static GTY ((deletable (""))) VEC(gimple,gc) *free_phinodes[NUM_BUCKETS - 2];
|
|
|
81 static unsigned long free_phinode_count;
|
|
|
82
|
|
|
83 static int ideal_phi_node_len (int);
|
|
|
84
|
|
|
85 #ifdef GATHER_STATISTICS
|
|
|
86 unsigned int phi_nodes_reused;
|
|
|
87 unsigned int phi_nodes_created;
|
|
|
88 #endif
|
|
|
89
|
|
|
90 /* Initialize management of PHIs. */
|
|
|
91
|
|
|
92 void
|
|
|
93 init_phinodes (void)
|
|
|
94 {
|
|
|
95 int i;
|
|
|
96
|
|
|
97 for (i = 0; i < NUM_BUCKETS - 2; i++)
|
|
|
98 free_phinodes[i] = NULL;
|
|
|
99 free_phinode_count = 0;
|
|
|
100 }
|
|
|
101
|
|
|
102 /* Finalize management of PHIs. */
|
|
|
103
|
|
|
104 void
|
|
|
105 fini_phinodes (void)
|
|
|
106 {
|
|
|
107 int i;
|
|
|
108
|
|
|
109 for (i = 0; i < NUM_BUCKETS - 2; i++)
|
|
|
110 free_phinodes[i] = NULL;
|
|
|
111 free_phinode_count = 0;
|
|
|
112 }
|
|
|
113
|
|
|
114 /* Dump some simple statistics regarding the re-use of PHI nodes. */
|
|
|
115
|
|
|
116 #ifdef GATHER_STATISTICS
|
|
|
117 void
|
|
|
118 phinodes_print_statistics (void)
|
|
|
119 {
|
|
|
120 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
|
|
|
121 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
|
|
|
122 }
|
|
|
123 #endif
|
|
|
124
|
|
|
125 /* Allocate a PHI node with at least LEN arguments. If the free list
|
|
|
126 happens to contain a PHI node with LEN arguments or more, return
|
|
|
127 that one. */
|
|
|
128
|
|
|
129 static inline gimple
|
|
|
130 allocate_phi_node (size_t len)
|
|
|
131 {
|
|
|
132 gimple phi;
|
|
|
133 size_t bucket = NUM_BUCKETS - 2;
|
|
|
134 size_t size = sizeof (struct gimple_statement_phi)
|
|
|
135 + (len - 1) * sizeof (struct phi_arg_d);
|
|
|
136
|
|
|
137 if (free_phinode_count)
|
|
|
138 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
|
|
|
139 if (free_phinodes[bucket])
|
|
|
140 break;
|
|
|
141
|
|
|
142 /* If our free list has an element, then use it. */
|
|
|
143 if (bucket < NUM_BUCKETS - 2
|
|
|
144 && gimple_phi_capacity (VEC_index (gimple, free_phinodes[bucket], 0))
|
|
|
145 >= len)
|
|
|
146 {
|
|
|
147 free_phinode_count--;
|
|
|
148 phi = VEC_pop (gimple, free_phinodes[bucket]);
|
|
|
149 if (VEC_empty (gimple, free_phinodes[bucket]))
|
|
|
150 VEC_free (gimple, gc, free_phinodes[bucket]);
|
|
|
151 #ifdef GATHER_STATISTICS
|
|
|
152 phi_nodes_reused++;
|
|
|
153 #endif
|
|
|
154 }
|
|
|
155 else
|
|
|
156 {
|
|
|
157 phi = (gimple) ggc_alloc (size);
|
|
|
158 #ifdef GATHER_STATISTICS
|
|
|
159 phi_nodes_created++;
|
|
|
160 {
|
|
|
161 enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
|
|
|
162 gimple_alloc_counts[(int) kind]++;
|
|
|
163 gimple_alloc_sizes[(int) kind] += size;
|
|
|
164 }
|
|
|
165 #endif
|
|
|
166 }
|
|
|
167
|
|
|
168 return phi;
|
|
|
169 }
|
|
|
170
|
|
|
171 /* Given LEN, the original number of requested PHI arguments, return
|
|
|
172 a new, "ideal" length for the PHI node. The "ideal" length rounds
|
|
|
173 the total size of the PHI node up to the next power of two bytes.
|
|
|
174
|
|
|
175 Rounding up will not result in wasting any memory since the size request
|
|
|
176 will be rounded up by the GC system anyway. [ Note this is not entirely
|
|
|
177 true since the original length might have fit on one of the special
|
|
|
178 GC pages. ] By rounding up, we may avoid the need to reallocate the
|
|
|
179 PHI node later if we increase the number of arguments for the PHI. */
|
|
|
180
|
|
|
181 static int
|
|
|
182 ideal_phi_node_len (int len)
|
|
|
183 {
|
|
|
184 size_t size, new_size;
|
|
|
185 int log2, new_len;
|
|
|
186
|
|
|
187 /* We do not support allocations of less than two PHI argument slots. */
|
|
|
188 if (len < 2)
|
|
|
189 len = 2;
|
|
|
190
|
|
|
191 /* Compute the number of bytes of the original request. */
|
|
|
192 size = sizeof (struct gimple_statement_phi)
|
|
|
193 + (len - 1) * sizeof (struct phi_arg_d);
|
|
|
194
|
|
|
195 /* Round it up to the next power of two. */
|
|
|
196 log2 = ceil_log2 (size);
|
|
|
197 new_size = 1 << log2;
|
|
|
198
|
|
|
199 /* Now compute and return the number of PHI argument slots given an
|
|
|
200 ideal size allocation. */
|
|
|
201 new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
|
|
|
202 return new_len;
|
|
|
203 }
|
|
|
204
|
|
|
205 /* Return a PHI node with LEN argument slots for variable VAR. */
|
|
|
206
|
|
|
207 gimple
|
|
|
208 make_phi_node (tree var, int len)
|
|
|
209 {
|
|
|
210 gimple phi;
|
|
|
211 int capacity, i;
|
|
|
212
|
|
|
213 capacity = ideal_phi_node_len (len);
|
|
|
214
|
|
|
215 phi = allocate_phi_node (capacity);
|
|
|
216
|
|
|
217 /* We need to clear the entire PHI node, including the argument
|
|
|
218 portion, because we represent a "missing PHI argument" by placing
|
|
|
219 NULL_TREE in PHI_ARG_DEF. */
|
|
|
220 memset (phi, 0, (sizeof (struct gimple_statement_phi)
|
|
|
221 - sizeof (struct phi_arg_d)
|
|
|
222 + sizeof (struct phi_arg_d) * len));
|
|
|
223 phi->gsbase.code = GIMPLE_PHI;
|
|
|
224 phi->gimple_phi.nargs = len;
|
|
|
225 phi->gimple_phi.capacity = capacity;
|
|
|
226 if (TREE_CODE (var) == SSA_NAME)
|
|
|
227 gimple_phi_set_result (phi, var);
|
|
|
228 else
|
|
|
229 gimple_phi_set_result (phi, make_ssa_name (var, phi));
|
|
|
230
|
|
|
231 for (i = 0; i < capacity; i++)
|
|
|
232 {
|
|
|
233 use_operand_p imm;
|
|
|
234 imm = gimple_phi_arg_imm_use_ptr (phi, i);
|
|
|
235 imm->use = gimple_phi_arg_def_ptr (phi, i);
|
|
|
236 imm->prev = NULL;
|
|
|
237 imm->next = NULL;
|
|
|
238 imm->loc.stmt = phi;
|
|
|
239 }
|
|
|
240
|
|
|
241 return phi;
|
|
|
242 }
|
|
|
243
|
|
|
244 /* We no longer need PHI, release it so that it may be reused. */
|
|
|
245
|
|
|
246 void
|
|
|
247 release_phi_node (gimple phi)
|
|
|
248 {
|
|
|
249 size_t bucket;
|
|
|
250 size_t len = gimple_phi_capacity (phi);
|
|
|
251 size_t x;
|
|
|
252
|
|
|
253 for (x = 0; x < gimple_phi_num_args (phi); x++)
|
|
|
254 {
|
|
|
255 use_operand_p imm;
|
|
|
256 imm = gimple_phi_arg_imm_use_ptr (phi, x);
|
|
|
257 delink_imm_use (imm);
|
|
|
258 }
|
|
|
259
|
|
|
260 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
|
|
|
261 bucket -= 2;
|
|
|
262 VEC_safe_push (gimple, gc, free_phinodes[bucket], phi);
|
|
|
263 free_phinode_count++;
|
|
|
264 }
|
|
|
265
|
|
|
266
|
|
|
267 /* Resize an existing PHI node. The only way is up. Return the
|
|
|
268 possibly relocated phi. */
|
|
|
269
|
|
|
270 static void
|
|
|
271 resize_phi_node (gimple *phi, size_t len)
|
|
|
272 {
|
|
|
273 size_t old_size, i;
|
|
|
274 gimple new_phi;
|
|
|
275
|
|
|
276 gcc_assert (len > gimple_phi_capacity (*phi));
|
|
|
277
|
|
|
278 /* The garbage collector will not look at the PHI node beyond the
|
|
|
279 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
|
|
|
280 portion of the PHI node currently in use. */
|
|
|
281 old_size = sizeof (struct gimple_statement_phi)
|
|
|
282 + (gimple_phi_num_args (*phi) - 1) * sizeof (struct phi_arg_d);
|
|
|
283
|
|
|
284 new_phi = allocate_phi_node (len);
|
|
|
285
|
|
|
286 memcpy (new_phi, *phi, old_size);
|
|
|
287
|
|
|
288 for (i = 0; i < gimple_phi_num_args (new_phi); i++)
|
|
|
289 {
|
|
|
290 use_operand_p imm, old_imm;
|
|
|
291 imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
|
|
|
292 old_imm = gimple_phi_arg_imm_use_ptr (*phi, i);
|
|
|
293 imm->use = gimple_phi_arg_def_ptr (new_phi, i);
|
|
|
294 relink_imm_use_stmt (imm, old_imm, new_phi);
|
|
|
295 }
|
|
|
296
|
|
|
297 new_phi->gimple_phi.capacity = len;
|
|
|
298
|
|
|
299 for (i = gimple_phi_num_args (new_phi); i < len; i++)
|
|
|
300 {
|
|
|
301 use_operand_p imm;
|
|
|
302 imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
|
|
|
303 imm->use = gimple_phi_arg_def_ptr (new_phi, i);
|
|
|
304 imm->prev = NULL;
|
|
|
305 imm->next = NULL;
|
|
|
306 imm->loc.stmt = new_phi;
|
|
|
307 }
|
|
|
308
|
|
|
309 *phi = new_phi;
|
|
|
310 }
|
|
|
311
|
|
|
312 /* Reserve PHI arguments for a new edge to basic block BB. */
|
|
|
313
|
|
|
314 void
|
|
|
315 reserve_phi_args_for_new_edge (basic_block bb)
|
|
|
316 {
|
|
|
317 size_t len = EDGE_COUNT (bb->preds);
|
|
|
318 size_t cap = ideal_phi_node_len (len + 4);
|
|
|
319 gimple_stmt_iterator gsi;
|
|
|
320
|
|
|
321 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
322 {
|
|
|
323 gimple *loc = gsi_stmt_ptr (&gsi);
|
|
|
324
|
|
|
325 if (len > gimple_phi_capacity (*loc))
|
|
|
326 {
|
|
|
327 gimple old_phi = *loc;
|
|
|
328
|
|
|
329 resize_phi_node (loc, cap);
|
|
|
330
|
|
|
331 /* The result of the PHI is defined by this PHI node. */
|
|
|
332 SSA_NAME_DEF_STMT (gimple_phi_result (*loc)) = *loc;
|
|
|
333
|
|
|
334 release_phi_node (old_phi);
|
|
|
335 }
|
|
|
336
|
|
|
337 /* We represent a "missing PHI argument" by placing NULL_TREE in
|
|
|
338 the corresponding slot. If PHI arguments were added
|
|
|
339 immediately after an edge is created, this zeroing would not
|
|
|
340 be necessary, but unfortunately this is not the case. For
|
|
|
341 example, the loop optimizer duplicates several basic blocks,
|
|
|
342 redirects edges, and then fixes up PHI arguments later in
|
|
|
343 batch. */
|
|
|
344 SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
|
|
|
345
|
|
|
346 (*loc)->gimple_phi.nargs++;
|
|
|
347 }
|
|
|
348 }
|
|
|
349
|
|
|
350 /* Adds PHI to BB. */
|
|
|
351
|
|
|
352 void
|
|
|
353 add_phi_node_to_bb (gimple phi, basic_block bb)
|
|
|
354 {
|
|
|
355 gimple_stmt_iterator gsi;
|
|
|
356 /* Add the new PHI node to the list of PHI nodes for block BB. */
|
|
|
357 if (phi_nodes (bb) == NULL)
|
|
|
358 set_phi_nodes (bb, gimple_seq_alloc ());
|
|
|
359
|
|
|
360 gsi = gsi_last (phi_nodes (bb));
|
|
|
361 gsi_insert_after (&gsi, phi, GSI_NEW_STMT);
|
|
|
362
|
|
|
363 /* Associate BB to the PHI node. */
|
|
|
364 gimple_set_bb (phi, bb);
|
|
|
365
|
|
|
366 }
|
|
|
367
|
|
|
368 /* Create a new PHI node for variable VAR at basic block BB. */
|
|
|
369
|
|
|
370 gimple
|
|
|
371 create_phi_node (tree var, basic_block bb)
|
|
|
372 {
|
|
|
373 gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds));
|
|
|
374
|
|
|
375 add_phi_node_to_bb (phi, bb);
|
|
|
376 return phi;
|
|
|
377 }
|
|
|
378
|
|
|
379
|
|
|
380 /* Add a new argument to PHI node PHI. DEF is the incoming reaching
|
|
|
381 definition and E is the edge through which DEF reaches PHI. The new
|
|
|
382 argument is added at the end of the argument list.
|
|
|
383 If PHI has reached its maximum capacity, add a few slots. In this case,
|
|
|
384 PHI points to the reallocated phi node when we return. */
|
|
|
385
|
|
|
386 void
|
|
|
387 add_phi_arg (gimple phi, tree def, edge e)
|
|
|
388 {
|
|
|
389 basic_block bb = e->dest;
|
|
|
390
|
|
|
391 gcc_assert (bb == gimple_bb (phi));
|
|
|
392
|
|
|
393 /* We resize PHI nodes upon edge creation. We should always have
|
|
|
394 enough room at this point. */
|
|
|
395 gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi));
|
|
|
396
|
|
|
397 /* We resize PHI nodes upon edge creation. We should always have
|
|
|
398 enough room at this point. */
|
|
|
399 gcc_assert (e->dest_idx < gimple_phi_num_args (phi));
|
|
|
400
|
|
|
401 /* Copy propagation needs to know what object occur in abnormal
|
|
|
402 PHI nodes. This is a convenient place to record such information. */
|
|
|
403 if (e->flags & EDGE_ABNORMAL)
|
|
|
404 {
|
|
|
405 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
|
|
|
406 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
|
|
|
407 }
|
|
|
408
|
|
|
409 SET_PHI_ARG_DEF (phi, e->dest_idx, def);
|
|
|
410 }
|
|
|
411
|
|
|
412
|
|
|
413 /* Remove the Ith argument from PHI's argument list. This routine
|
|
|
414 implements removal by swapping the last alternative with the
|
|
|
415 alternative we want to delete and then shrinking the vector, which
|
|
|
416 is consistent with how we remove an edge from the edge vector. */
|
|
|
417
|
|
|
418 static void
|
|
|
419 remove_phi_arg_num (gimple phi, int i)
|
|
|
420 {
|
|
|
421 int num_elem = gimple_phi_num_args (phi);
|
|
|
422
|
|
|
423 gcc_assert (i < num_elem);
|
|
|
424
|
|
|
425 /* Delink the item which is being removed. */
|
|
|
426 delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i));
|
|
|
427
|
|
|
428 /* If it is not the last element, move the last element
|
|
|
429 to the element we want to delete, resetting all the links. */
|
|
|
430 if (i != num_elem - 1)
|
|
|
431 {
|
|
|
432 use_operand_p old_p, new_p;
|
|
|
433 old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
|
|
|
434 new_p = gimple_phi_arg_imm_use_ptr (phi, i);
|
|
|
435 /* Set use on new node, and link into last element's place. */
|
|
|
436 *(new_p->use) = *(old_p->use);
|
|
|
437 relink_imm_use (new_p, old_p);
|
|
|
438 }
|
|
|
439
|
|
|
440 /* Shrink the vector and return. Note that we do not have to clear
|
|
|
441 PHI_ARG_DEF because the garbage collector will not look at those
|
|
|
442 elements beyond the first PHI_NUM_ARGS elements of the array. */
|
|
|
443 phi->gimple_phi.nargs--;
|
|
|
444 }
|
|
|
445
|
|
|
446
|
|
|
447 /* Remove all PHI arguments associated with edge E. */
|
|
|
448
|
|
|
449 void
|
|
|
450 remove_phi_args (edge e)
|
|
|
451 {
|
|
|
452 gimple_stmt_iterator gsi;
|
|
|
453
|
|
|
454 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
455 remove_phi_arg_num (gsi_stmt (gsi), e->dest_idx);
|
|
|
456 }
|
|
|
457
|
|
|
458
|
|
|
459 /* Remove the PHI node pointed-to by iterator GSI from basic block BB. After
|
|
|
460 removal, iterator GSI is updated to point to the next PHI node in the
|
|
|
461 sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released
|
|
|
462 into the free pool of SSA names. */
|
|
|
463
|
|
|
464 void
|
|
|
465 remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
|
|
|
466 {
|
|
|
467 gimple phi = gsi_stmt (*gsi);
|
|
|
468 gsi_remove (gsi, false);
|
|
|
469
|
|
|
470 /* If we are deleting the PHI node, then we should release the
|
|
|
471 SSA_NAME node so that it can be reused. */
|
|
|
472 release_phi_node (phi);
|
|
|
473 if (release_lhs_p)
|
|
|
474 release_ssa_name (gimple_phi_result (phi));
|
|
|
475 }
|
|
|
476
|
|
|
477 /* Remove all the phi nodes from BB. */
|
|
|
478
|
|
|
479 void
|
|
|
480 remove_phi_nodes (basic_block bb)
|
|
|
481 {
|
|
|
482 gimple_stmt_iterator gsi;
|
|
|
483
|
|
|
484 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
|
|
|
485 remove_phi_node (&gsi, true);
|
|
|
486
|
|
|
487 set_phi_nodes (bb, NULL);
|
|
|
488 }
|
|
|
489
|
|
|
490 #include "gt-tree-phinodes.h"
|
