|
0
|
1 /* Convert a program in SSA form into Normal form.
|
|
|
2 Copyright (C) 2004, 2005, 2006, 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 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "ggc.h"
|
|
|
27 #include "basic-block.h"
|
|
|
28 #include "diagnostic.h"
|
|
|
29 #include "bitmap.h"
|
|
|
30 #include "tree-flow.h"
|
|
|
31 #include "timevar.h"
|
|
|
32 #include "tree-dump.h"
|
|
|
33 #include "tree-ssa-live.h"
|
|
|
34 #include "tree-pass.h"
|
|
|
35 #include "toplev.h"
|
|
|
36
|
|
|
37
|
|
|
38 /* Used to hold all the components required to do SSA PHI elimination.
|
|
|
39 The node and pred/succ list is a simple linear list of nodes and
|
|
|
40 edges represented as pairs of nodes.
|
|
|
41
|
|
|
42 The predecessor and successor list: Nodes are entered in pairs, where
|
|
|
43 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
|
|
|
44 predecessors, all the odd elements are successors.
|
|
|
45
|
|
|
46 Rationale:
|
|
|
47 When implemented as bitmaps, very large programs SSA->Normal times were
|
|
|
48 being dominated by clearing the interference graph.
|
|
|
49
|
|
|
50 Typically this list of edges is extremely small since it only includes
|
|
|
51 PHI results and uses from a single edge which have not coalesced with
|
|
|
52 each other. This means that no virtual PHI nodes are included, and
|
|
|
53 empirical evidence suggests that the number of edges rarely exceed
|
|
|
54 3, and in a bootstrap of GCC, the maximum size encountered was 7.
|
|
|
55 This also limits the number of possible nodes that are involved to
|
|
|
56 rarely more than 6, and in the bootstrap of gcc, the maximum number
|
|
|
57 of nodes encountered was 12. */
|
|
|
58
|
|
|
59 typedef struct _elim_graph {
|
|
|
60 /* Size of the elimination vectors. */
|
|
|
61 int size;
|
|
|
62
|
|
|
63 /* List of nodes in the elimination graph. */
|
|
|
64 VEC(tree,heap) *nodes;
|
|
|
65
|
|
|
66 /* The predecessor and successor edge list. */
|
|
|
67 VEC(int,heap) *edge_list;
|
|
|
68
|
|
|
69 /* Visited vector. */
|
|
|
70 sbitmap visited;
|
|
|
71
|
|
|
72 /* Stack for visited nodes. */
|
|
|
73 VEC(int,heap) *stack;
|
|
|
74
|
|
|
75 /* The variable partition map. */
|
|
|
76 var_map map;
|
|
|
77
|
|
|
78 /* Edge being eliminated by this graph. */
|
|
|
79 edge e;
|
|
|
80
|
|
|
81 /* List of constant copies to emit. These are pushed on in pairs. */
|
|
|
82 VEC(tree,heap) *const_copies;
|
|
|
83 } *elim_graph;
|
|
|
84
|
|
|
85
|
|
|
86 /* Create a temporary variable based on the type of variable T. Use T's name
|
|
|
87 as the prefix. */
|
|
|
88
|
|
|
89 static tree
|
|
|
90 create_temp (tree t)
|
|
|
91 {
|
|
|
92 tree tmp;
|
|
|
93 const char *name = NULL;
|
|
|
94 tree type;
|
|
|
95
|
|
|
96 if (TREE_CODE (t) == SSA_NAME)
|
|
|
97 t = SSA_NAME_VAR (t);
|
|
|
98
|
|
|
99 gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
|
|
|
100
|
|
|
101 type = TREE_TYPE (t);
|
|
|
102 tmp = DECL_NAME (t);
|
|
|
103 if (tmp)
|
|
|
104 name = IDENTIFIER_POINTER (tmp);
|
|
|
105
|
|
|
106 if (name == NULL)
|
|
|
107 name = "temp";
|
|
|
108 tmp = create_tmp_var (type, name);
|
|
|
109
|
|
|
110 if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
|
|
|
111 {
|
|
|
112 SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
|
|
|
113 DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
|
|
|
114 }
|
|
|
115 else if (!DECL_IGNORED_P (t))
|
|
|
116 {
|
|
|
117 SET_DECL_DEBUG_EXPR (tmp, t);
|
|
|
118 DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
|
|
|
119 }
|
|
|
120 DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
|
|
|
121 DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
|
|
|
122 DECL_GIMPLE_REG_P (tmp) = DECL_GIMPLE_REG_P (t);
|
|
|
123 add_referenced_var (tmp);
|
|
|
124
|
|
|
125 /* add_referenced_var will create the annotation and set up some
|
|
|
126 of the flags in the annotation. However, some flags we need to
|
|
|
127 inherit from our original variable. */
|
|
|
128 set_symbol_mem_tag (tmp, symbol_mem_tag (t));
|
|
|
129 if (is_call_clobbered (t))
|
|
|
130 mark_call_clobbered (tmp, var_ann (t)->escape_mask);
|
|
|
131 if (bitmap_bit_p (gimple_call_used_vars (cfun), DECL_UID (t)))
|
|
|
132 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (tmp));
|
|
|
133
|
|
|
134 return tmp;
|
|
|
135 }
|
|
|
136
|
|
|
137
|
|
|
138 /* This helper function fill insert a copy from a constant or variable SRC to
|
|
|
139 variable DEST on edge E. */
|
|
|
140
|
|
|
141 static void
|
|
|
142 insert_copy_on_edge (edge e, tree dest, tree src)
|
|
|
143 {
|
|
|
144 gimple copy;
|
|
|
145
|
|
|
146 copy = gimple_build_assign (dest, src);
|
|
|
147 set_is_used (dest);
|
|
|
148
|
|
|
149 if (TREE_CODE (src) == ADDR_EXPR)
|
|
|
150 src = TREE_OPERAND (src, 0);
|
|
|
151 if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
|
|
|
152 set_is_used (src);
|
|
|
153
|
|
|
154 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
155 {
|
|
|
156 fprintf (dump_file,
|
|
|
157 "Inserting a copy on edge BB%d->BB%d :",
|
|
|
158 e->src->index,
|
|
|
159 e->dest->index);
|
|
|
160 print_gimple_stmt (dump_file, copy, 0, dump_flags);
|
|
|
161 fprintf (dump_file, "\n");
|
|
|
162 }
|
|
|
163
|
|
|
164 gsi_insert_on_edge (e, copy);
|
|
|
165 }
|
|
|
166
|
|
|
167
|
|
|
168 /* Create an elimination graph with SIZE nodes and associated data
|
|
|
169 structures. */
|
|
|
170
|
|
|
171 static elim_graph
|
|
|
172 new_elim_graph (int size)
|
|
|
173 {
|
|
|
174 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
|
|
|
175
|
|
|
176 g->nodes = VEC_alloc (tree, heap, 30);
|
|
|
177 g->const_copies = VEC_alloc (tree, heap, 20);
|
|
|
178 g->edge_list = VEC_alloc (int, heap, 20);
|
|
|
179 g->stack = VEC_alloc (int, heap, 30);
|
|
|
180
|
|
|
181 g->visited = sbitmap_alloc (size);
|
|
|
182
|
|
|
183 return g;
|
|
|
184 }
|
|
|
185
|
|
|
186
|
|
|
187 /* Empty elimination graph G. */
|
|
|
188
|
|
|
189 static inline void
|
|
|
190 clear_elim_graph (elim_graph g)
|
|
|
191 {
|
|
|
192 VEC_truncate (tree, g->nodes, 0);
|
|
|
193 VEC_truncate (int, g->edge_list, 0);
|
|
|
194 }
|
|
|
195
|
|
|
196
|
|
|
197 /* Delete elimination graph G. */
|
|
|
198
|
|
|
199 static inline void
|
|
|
200 delete_elim_graph (elim_graph g)
|
|
|
201 {
|
|
|
202 sbitmap_free (g->visited);
|
|
|
203 VEC_free (int, heap, g->stack);
|
|
|
204 VEC_free (int, heap, g->edge_list);
|
|
|
205 VEC_free (tree, heap, g->const_copies);
|
|
|
206 VEC_free (tree, heap, g->nodes);
|
|
|
207 free (g);
|
|
|
208 }
|
|
|
209
|
|
|
210
|
|
|
211 /* Return the number of nodes in graph G. */
|
|
|
212
|
|
|
213 static inline int
|
|
|
214 elim_graph_size (elim_graph g)
|
|
|
215 {
|
|
|
216 return VEC_length (tree, g->nodes);
|
|
|
217 }
|
|
|
218
|
|
|
219
|
|
|
220 /* Add NODE to graph G, if it doesn't exist already. */
|
|
|
221
|
|
|
222 static inline void
|
|
|
223 elim_graph_add_node (elim_graph g, tree node)
|
|
|
224 {
|
|
|
225 int x;
|
|
|
226 tree t;
|
|
|
227
|
|
|
228 for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
|
|
|
229 if (t == node)
|
|
|
230 return;
|
|
|
231 VEC_safe_push (tree, heap, g->nodes, node);
|
|
|
232 }
|
|
|
233
|
|
|
234
|
|
|
235 /* Add the edge PRED->SUCC to graph G. */
|
|
|
236
|
|
|
237 static inline void
|
|
|
238 elim_graph_add_edge (elim_graph g, int pred, int succ)
|
|
|
239 {
|
|
|
240 VEC_safe_push (int, heap, g->edge_list, pred);
|
|
|
241 VEC_safe_push (int, heap, g->edge_list, succ);
|
|
|
242 }
|
|
|
243
|
|
|
244
|
|
|
245 /* Remove an edge from graph G for which NODE is the predecessor, and
|
|
|
246 return the successor node. -1 is returned if there is no such edge. */
|
|
|
247
|
|
|
248 static inline int
|
|
|
249 elim_graph_remove_succ_edge (elim_graph g, int node)
|
|
|
250 {
|
|
|
251 int y;
|
|
|
252 unsigned x;
|
|
|
253 for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
|
|
|
254 if (VEC_index (int, g->edge_list, x) == node)
|
|
|
255 {
|
|
|
256 VEC_replace (int, g->edge_list, x, -1);
|
|
|
257 y = VEC_index (int, g->edge_list, x + 1);
|
|
|
258 VEC_replace (int, g->edge_list, x + 1, -1);
|
|
|
259 return y;
|
|
|
260 }
|
|
|
261 return -1;
|
|
|
262 }
|
|
|
263
|
|
|
264
|
|
|
265 /* Find all the nodes in GRAPH which are successors to NODE in the
|
|
|
266 edge list. VAR will hold the partition number found. CODE is the
|
|
|
267 code fragment executed for every node found. */
|
|
|
268
|
|
|
269 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
|
|
|
270 do { \
|
|
|
271 unsigned x_; \
|
|
|
272 int y_; \
|
|
|
273 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
|
|
|
274 { \
|
|
|
275 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
|
|
|
276 if (y_ != (NODE)) \
|
|
|
277 continue; \
|
|
|
278 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
|
|
|
279 CODE; \
|
|
|
280 } \
|
|
|
281 } while (0)
|
|
|
282
|
|
|
283
|
|
|
284 /* Find all the nodes which are predecessors of NODE in the edge list for
|
|
|
285 GRAPH. VAR will hold the partition number found. CODE is the
|
|
|
286 code fragment executed for every node found. */
|
|
|
287
|
|
|
288 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
|
|
|
289 do { \
|
|
|
290 unsigned x_; \
|
|
|
291 int y_; \
|
|
|
292 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
|
|
|
293 { \
|
|
|
294 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
|
|
|
295 if (y_ != (NODE)) \
|
|
|
296 continue; \
|
|
|
297 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
|
|
|
298 CODE; \
|
|
|
299 } \
|
|
|
300 } while (0)
|
|
|
301
|
|
|
302
|
|
|
303 /* Add T to elimination graph G. */
|
|
|
304
|
|
|
305 static inline void
|
|
|
306 eliminate_name (elim_graph g, tree T)
|
|
|
307 {
|
|
|
308 elim_graph_add_node (g, T);
|
|
|
309 }
|
|
|
310
|
|
|
311
|
|
|
312 /* Build elimination graph G for basic block BB on incoming PHI edge
|
|
|
313 G->e. */
|
|
|
314
|
|
|
315 static void
|
|
|
316 eliminate_build (elim_graph g, basic_block B)
|
|
|
317 {
|
|
|
318 tree T0, Ti;
|
|
|
319 int p0, pi;
|
|
|
320 gimple_stmt_iterator gsi;
|
|
|
321
|
|
|
322 clear_elim_graph (g);
|
|
|
323
|
|
|
324 for (gsi = gsi_start_phis (B); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
325 {
|
|
|
326 gimple phi = gsi_stmt (gsi);
|
|
|
327
|
|
|
328 T0 = var_to_partition_to_var (g->map, gimple_phi_result (phi));
|
|
|
329
|
|
|
330 /* Ignore results which are not in partitions. */
|
|
|
331 if (T0 == NULL_TREE)
|
|
|
332 continue;
|
|
|
333
|
|
|
334 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
|
|
|
335
|
|
|
336 /* If this argument is a constant, or a SSA_NAME which is being
|
|
|
337 left in SSA form, just queue a copy to be emitted on this
|
|
|
338 edge. */
|
|
|
339 if (!phi_ssa_name_p (Ti)
|
|
|
340 || (TREE_CODE (Ti) == SSA_NAME
|
|
|
341 && var_to_partition (g->map, Ti) == NO_PARTITION))
|
|
|
342 {
|
|
|
343 /* Save constant copies until all other copies have been emitted
|
|
|
344 on this edge. */
|
|
|
345 VEC_safe_push (tree, heap, g->const_copies, T0);
|
|
|
346 VEC_safe_push (tree, heap, g->const_copies, Ti);
|
|
|
347 }
|
|
|
348 else
|
|
|
349 {
|
|
|
350 Ti = var_to_partition_to_var (g->map, Ti);
|
|
|
351 if (T0 != Ti)
|
|
|
352 {
|
|
|
353 eliminate_name (g, T0);
|
|
|
354 eliminate_name (g, Ti);
|
|
|
355 p0 = var_to_partition (g->map, T0);
|
|
|
356 pi = var_to_partition (g->map, Ti);
|
|
|
357 elim_graph_add_edge (g, p0, pi);
|
|
|
358 }
|
|
|
359 }
|
|
|
360 }
|
|
|
361 }
|
|
|
362
|
|
|
363
|
|
|
364 /* Push successors of T onto the elimination stack for G. */
|
|
|
365
|
|
|
366 static void
|
|
|
367 elim_forward (elim_graph g, int T)
|
|
|
368 {
|
|
|
369 int S;
|
|
|
370 SET_BIT (g->visited, T);
|
|
|
371 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
|
|
|
372 {
|
|
|
373 if (!TEST_BIT (g->visited, S))
|
|
|
374 elim_forward (g, S);
|
|
|
375 });
|
|
|
376 VEC_safe_push (int, heap, g->stack, T);
|
|
|
377 }
|
|
|
378
|
|
|
379
|
|
|
380 /* Return 1 if there unvisited predecessors of T in graph G. */
|
|
|
381
|
|
|
382 static int
|
|
|
383 elim_unvisited_predecessor (elim_graph g, int T)
|
|
|
384 {
|
|
|
385 int P;
|
|
|
386 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
|
|
|
387 {
|
|
|
388 if (!TEST_BIT (g->visited, P))
|
|
|
389 return 1;
|
|
|
390 });
|
|
|
391 return 0;
|
|
|
392 }
|
|
|
393
|
|
|
394 /* Process predecessors first, and insert a copy. */
|
|
|
395
|
|
|
396 static void
|
|
|
397 elim_backward (elim_graph g, int T)
|
|
|
398 {
|
|
|
399 int P;
|
|
|
400 SET_BIT (g->visited, T);
|
|
|
401 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
|
|
|
402 {
|
|
|
403 if (!TEST_BIT (g->visited, P))
|
|
|
404 {
|
|
|
405 elim_backward (g, P);
|
|
|
406 insert_copy_on_edge (g->e,
|
|
|
407 partition_to_var (g->map, P),
|
|
|
408 partition_to_var (g->map, T));
|
|
|
409 }
|
|
|
410 });
|
|
|
411 }
|
|
|
412
|
|
|
413 /* Insert required copies for T in graph G. Check for a strongly connected
|
|
|
414 region, and create a temporary to break the cycle if one is found. */
|
|
|
415
|
|
|
416 static void
|
|
|
417 elim_create (elim_graph g, int T)
|
|
|
418 {
|
|
|
419 tree U;
|
|
|
420 int P, S;
|
|
|
421
|
|
|
422 if (elim_unvisited_predecessor (g, T))
|
|
|
423 {
|
|
|
424 U = create_temp (partition_to_var (g->map, T));
|
|
|
425 insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
|
|
|
426 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
|
|
|
427 {
|
|
|
428 if (!TEST_BIT (g->visited, P))
|
|
|
429 {
|
|
|
430 elim_backward (g, P);
|
|
|
431 insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
|
|
|
432 }
|
|
|
433 });
|
|
|
434 }
|
|
|
435 else
|
|
|
436 {
|
|
|
437 S = elim_graph_remove_succ_edge (g, T);
|
|
|
438 if (S != -1)
|
|
|
439 {
|
|
|
440 SET_BIT (g->visited, T);
|
|
|
441 insert_copy_on_edge (g->e,
|
|
|
442 partition_to_var (g->map, T),
|
|
|
443 partition_to_var (g->map, S));
|
|
|
444 }
|
|
|
445 }
|
|
|
446
|
|
|
447 }
|
|
|
448
|
|
|
449
|
|
|
450 /* Eliminate all the phi nodes on edge E in graph G. */
|
|
|
451
|
|
|
452 static void
|
|
|
453 eliminate_phi (edge e, elim_graph g)
|
|
|
454 {
|
|
|
455 int x;
|
|
|
456 basic_block B = e->dest;
|
|
|
457
|
|
|
458 gcc_assert (VEC_length (tree, g->const_copies) == 0);
|
|
|
459
|
|
|
460 /* Abnormal edges already have everything coalesced. */
|
|
|
461 if (e->flags & EDGE_ABNORMAL)
|
|
|
462 return;
|
|
|
463
|
|
|
464 g->e = e;
|
|
|
465
|
|
|
466 eliminate_build (g, B);
|
|
|
467
|
|
|
468 if (elim_graph_size (g) != 0)
|
|
|
469 {
|
|
|
470 tree var;
|
|
|
471
|
|
|
472 sbitmap_zero (g->visited);
|
|
|
473 VEC_truncate (int, g->stack, 0);
|
|
|
474
|
|
|
475 for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
|
|
|
476 {
|
|
|
477 int p = var_to_partition (g->map, var);
|
|
|
478 if (!TEST_BIT (g->visited, p))
|
|
|
479 elim_forward (g, p);
|
|
|
480 }
|
|
|
481
|
|
|
482 sbitmap_zero (g->visited);
|
|
|
483 while (VEC_length (int, g->stack) > 0)
|
|
|
484 {
|
|
|
485 x = VEC_pop (int, g->stack);
|
|
|
486 if (!TEST_BIT (g->visited, x))
|
|
|
487 elim_create (g, x);
|
|
|
488 }
|
|
|
489 }
|
|
|
490
|
|
|
491 /* If there are any pending constant copies, issue them now. */
|
|
|
492 while (VEC_length (tree, g->const_copies) > 0)
|
|
|
493 {
|
|
|
494 tree src, dest;
|
|
|
495 src = VEC_pop (tree, g->const_copies);
|
|
|
496 dest = VEC_pop (tree, g->const_copies);
|
|
|
497 insert_copy_on_edge (e, dest, src);
|
|
|
498 }
|
|
|
499 }
|
|
|
500
|
|
|
501
|
|
|
502 /* Take the ssa-name var_map MAP, and assign real variables to each
|
|
|
503 partition. */
|
|
|
504
|
|
|
505 static void
|
|
|
506 assign_vars (var_map map)
|
|
|
507 {
|
|
|
508 int x, num;
|
|
|
509 tree var, root;
|
|
|
510 var_ann_t ann;
|
|
|
511
|
|
|
512 num = num_var_partitions (map);
|
|
|
513 for (x = 0; x < num; x++)
|
|
|
514 {
|
|
|
515 var = partition_to_var (map, x);
|
|
|
516 if (TREE_CODE (var) != SSA_NAME)
|
|
|
517 {
|
|
|
518 ann = var_ann (var);
|
|
|
519 /* It must already be coalesced. */
|
|
|
520 gcc_assert (ann->out_of_ssa_tag == 1);
|
|
|
521 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
522 {
|
|
|
523 fprintf (dump_file, "partition %d already has variable ", x);
|
|
|
524 print_generic_expr (dump_file, var, TDF_SLIM);
|
|
|
525 fprintf (dump_file, " assigned to it.\n");
|
|
|
526 }
|
|
|
527 }
|
|
|
528 else
|
|
|
529 {
|
|
|
530 root = SSA_NAME_VAR (var);
|
|
|
531 ann = var_ann (root);
|
|
|
532 /* If ROOT is already associated, create a new one. */
|
|
|
533 if (ann->out_of_ssa_tag)
|
|
|
534 {
|
|
|
535 root = create_temp (root);
|
|
|
536 ann = var_ann (root);
|
|
|
537 }
|
|
|
538 /* ROOT has not been coalesced yet, so use it. */
|
|
|
539 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
540 {
|
|
|
541 fprintf (dump_file, "Partition %d is assigned to var ", x);
|
|
|
542 print_generic_stmt (dump_file, root, TDF_SLIM);
|
|
|
543 }
|
|
|
544 change_partition_var (map, root, x);
|
|
|
545 }
|
|
|
546 }
|
|
|
547 }
|
|
|
548
|
|
|
549
|
|
|
550 /* Replace use operand P with whatever variable it has been rewritten to based
|
|
|
551 on the partitions in MAP. EXPR is an optional expression vector over SSA
|
|
|
552 versions which is used to replace P with an expression instead of a variable.
|
|
|
553 If the stmt is changed, return true. */
|
|
|
554
|
|
|
555 static inline bool
|
|
|
556 replace_use_variable (var_map map, use_operand_p p, gimple *expr)
|
|
|
557 {
|
|
|
558 tree new_var;
|
|
|
559 tree var = USE_FROM_PTR (p);
|
|
|
560
|
|
|
561 /* Check if we are replacing this variable with an expression. */
|
|
|
562 if (expr)
|
|
|
563 {
|
|
|
564 int version = SSA_NAME_VERSION (var);
|
|
|
565 if (expr[version])
|
|
|
566 {
|
|
|
567 SET_USE (p, gimple_assign_rhs_to_tree (expr[version]));
|
|
|
568 return true;
|
|
|
569 }
|
|
|
570 }
|
|
|
571
|
|
|
572 new_var = var_to_partition_to_var (map, var);
|
|
|
573 if (new_var)
|
|
|
574 {
|
|
|
575 SET_USE (p, new_var);
|
|
|
576 set_is_used (new_var);
|
|
|
577 return true;
|
|
|
578 }
|
|
|
579 return false;
|
|
|
580 }
|
|
|
581
|
|
|
582
|
|
|
583 /* Replace def operand DEF_P with whatever variable it has been rewritten to
|
|
|
584 based on the partitions in MAP. EXPR is an optional expression vector over
|
|
|
585 SSA versions which is used to replace DEF_P with an expression instead of a
|
|
|
586 variable. If the stmt is changed, return true. */
|
|
|
587
|
|
|
588 static inline bool
|
|
|
589 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
|
|
|
590 {
|
|
|
591 tree new_var;
|
|
|
592 tree var = DEF_FROM_PTR (def_p);
|
|
|
593
|
|
|
594 /* Do nothing if we are replacing this variable with an expression. */
|
|
|
595 if (expr && expr[SSA_NAME_VERSION (var)])
|
|
|
596 return true;
|
|
|
597
|
|
|
598 new_var = var_to_partition_to_var (map, var);
|
|
|
599 if (new_var)
|
|
|
600 {
|
|
|
601 SET_DEF (def_p, new_var);
|
|
|
602 set_is_used (new_var);
|
|
|
603 return true;
|
|
|
604 }
|
|
|
605 return false;
|
|
|
606 }
|
|
|
607
|
|
|
608
|
|
|
609 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
|
|
|
610 check to see if this allows another PHI node to be removed. */
|
|
|
611
|
|
|
612 static void
|
|
|
613 remove_gimple_phi_args (gimple phi)
|
|
|
614 {
|
|
|
615 use_operand_p arg_p;
|
|
|
616 ssa_op_iter iter;
|
|
|
617
|
|
|
618 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
619 {
|
|
|
620 fprintf (dump_file, "Removing Dead PHI definition: ");
|
|
|
621 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
|
|
622 }
|
|
|
623
|
|
|
624 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
|
|
|
625 {
|
|
|
626 tree arg = USE_FROM_PTR (arg_p);
|
|
|
627 if (TREE_CODE (arg) == SSA_NAME)
|
|
|
628 {
|
|
|
629 /* Remove the reference to the existing argument. */
|
|
|
630 SET_USE (arg_p, NULL_TREE);
|
|
|
631 if (has_zero_uses (arg))
|
|
|
632 {
|
|
|
633 gimple stmt;
|
|
|
634 gimple_stmt_iterator gsi;
|
|
|
635
|
|
|
636 stmt = SSA_NAME_DEF_STMT (arg);
|
|
|
637
|
|
|
638 /* Also remove the def if it is a PHI node. */
|
|
|
639 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
640 {
|
|
|
641 remove_gimple_phi_args (stmt);
|
|
|
642 gsi = gsi_for_stmt (stmt);
|
|
|
643 remove_phi_node (&gsi, true);
|
|
|
644 }
|
|
|
645
|
|
|
646 }
|
|
|
647 }
|
|
|
648 }
|
|
|
649 }
|
|
|
650
|
|
|
651 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
|
|
|
652
|
|
|
653 static void
|
|
|
654 eliminate_useless_phis (void)
|
|
|
655 {
|
|
|
656 basic_block bb;
|
|
|
657 gimple_stmt_iterator gsi;
|
|
|
658 tree result;
|
|
|
659
|
|
|
660 FOR_EACH_BB (bb)
|
|
|
661 {
|
|
|
662 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
|
|
|
663 {
|
|
|
664 gimple phi = gsi_stmt (gsi);
|
|
|
665 result = gimple_phi_result (phi);
|
|
|
666 if (!is_gimple_reg (SSA_NAME_VAR (result)))
|
|
|
667 {
|
|
|
668 #ifdef ENABLE_CHECKING
|
|
|
669 size_t i;
|
|
|
670 /* There should be no arguments which are not virtual, or the
|
|
|
671 results will be incorrect. */
|
|
|
672 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
673 {
|
|
|
674 tree arg = PHI_ARG_DEF (phi, i);
|
|
|
675 if (TREE_CODE (arg) == SSA_NAME
|
|
|
676 && is_gimple_reg (SSA_NAME_VAR (arg)))
|
|
|
677 {
|
|
|
678 fprintf (stderr, "Argument of PHI is not virtual (");
|
|
|
679 print_generic_expr (stderr, arg, TDF_SLIM);
|
|
|
680 fprintf (stderr, "), but the result is :");
|
|
|
681 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
|
|
|
682 internal_error ("SSA corruption");
|
|
|
683 }
|
|
|
684 }
|
|
|
685 #endif
|
|
|
686 remove_phi_node (&gsi, true);
|
|
|
687 }
|
|
|
688 else
|
|
|
689 {
|
|
|
690 /* Also remove real PHIs with no uses. */
|
|
|
691 if (has_zero_uses (result))
|
|
|
692 {
|
|
|
693 remove_gimple_phi_args (phi);
|
|
|
694 remove_phi_node (&gsi, true);
|
|
|
695 }
|
|
|
696 else
|
|
|
697 gsi_next (&gsi);
|
|
|
698 }
|
|
|
699 }
|
|
|
700 }
|
|
|
701 }
|
|
|
702
|
|
|
703
|
|
|
704 /* This function will rewrite the current program using the variable mapping
|
|
|
705 found in MAP. If the replacement vector VALUES is provided, any
|
|
|
706 occurrences of partitions with non-null entries in the vector will be
|
|
|
707 replaced with the expression in the vector instead of its mapped
|
|
|
708 variable. */
|
|
|
709
|
|
|
710 static void
|
|
|
711 rewrite_trees (var_map map, gimple *values)
|
|
|
712 {
|
|
|
713 elim_graph g;
|
|
|
714 basic_block bb;
|
|
|
715 gimple_stmt_iterator gsi;
|
|
|
716 edge e;
|
|
|
717 gimple_seq phi;
|
|
|
718 bool changed;
|
|
|
719
|
|
|
720 #ifdef ENABLE_CHECKING
|
|
|
721 /* Search for PHIs where the destination has no partition, but one
|
|
|
722 or more arguments has a partition. This should not happen and can
|
|
|
723 create incorrect code. */
|
|
|
724 FOR_EACH_BB (bb)
|
|
|
725 {
|
|
|
726 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
727 {
|
|
|
728 gimple phi = gsi_stmt (gsi);
|
|
|
729 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
|
|
|
730 if (T0 == NULL_TREE)
|
|
|
731 {
|
|
|
732 size_t i;
|
|
|
733 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
734 {
|
|
|
735 tree arg = PHI_ARG_DEF (phi, i);
|
|
|
736
|
|
|
737 if (TREE_CODE (arg) == SSA_NAME
|
|
|
738 && var_to_partition (map, arg) != NO_PARTITION)
|
|
|
739 {
|
|
|
740 fprintf (stderr, "Argument of PHI is in a partition :(");
|
|
|
741 print_generic_expr (stderr, arg, TDF_SLIM);
|
|
|
742 fprintf (stderr, "), but the result is not :");
|
|
|
743 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
|
|
|
744 internal_error ("SSA corruption");
|
|
|
745 }
|
|
|
746 }
|
|
|
747 }
|
|
|
748 }
|
|
|
749 }
|
|
|
750 #endif
|
|
|
751
|
|
|
752 /* Replace PHI nodes with any required copies. */
|
|
|
753 g = new_elim_graph (map->num_partitions);
|
|
|
754 g->map = map;
|
|
|
755 FOR_EACH_BB (bb)
|
|
|
756 {
|
|
|
757 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
|
|
|
758 {
|
|
|
759 gimple stmt = gsi_stmt (gsi);
|
|
|
760 use_operand_p use_p, copy_use_p;
|
|
|
761 def_operand_p def_p;
|
|
|
762 bool remove = false, is_copy = false;
|
|
|
763 int num_uses = 0;
|
|
|
764 ssa_op_iter iter;
|
|
|
765
|
|
|
766 changed = false;
|
|
|
767
|
|
|
768 if (gimple_assign_copy_p (stmt))
|
|
|
769 is_copy = true;
|
|
|
770
|
|
|
771 copy_use_p = NULL_USE_OPERAND_P;
|
|
|
772 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
|
|
|
773 {
|
|
|
774 if (replace_use_variable (map, use_p, values))
|
|
|
775 changed = true;
|
|
|
776 copy_use_p = use_p;
|
|
|
777 num_uses++;
|
|
|
778 }
|
|
|
779
|
|
|
780 if (num_uses != 1)
|
|
|
781 is_copy = false;
|
|
|
782
|
|
|
783 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
|
|
|
784
|
|
|
785 if (def_p != NULL)
|
|
|
786 {
|
|
|
787 /* Mark this stmt for removal if it is the list of replaceable
|
|
|
788 expressions. */
|
|
|
789 if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
|
|
|
790 remove = true;
|
|
|
791 else
|
|
|
792 {
|
|
|
793 if (replace_def_variable (map, def_p, NULL))
|
|
|
794 changed = true;
|
|
|
795 /* If both SSA_NAMEs coalesce to the same variable,
|
|
|
796 mark the now redundant copy for removal. */
|
|
|
797 if (is_copy)
|
|
|
798 {
|
|
|
799 gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
|
|
|
800 if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
|
|
|
801 remove = true;
|
|
|
802 }
|
|
|
803 }
|
|
|
804 }
|
|
|
805 else
|
|
|
806 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
|
|
|
807 if (replace_def_variable (map, def_p, NULL))
|
|
|
808 changed = true;
|
|
|
809
|
|
|
810 /* Remove any stmts marked for removal. */
|
|
|
811 if (remove)
|
|
|
812 gsi_remove (&gsi, true);
|
|
|
813 else
|
|
|
814 {
|
|
|
815 if (changed)
|
|
|
816 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
|
|
|
817 gimple_purge_dead_eh_edges (bb);
|
|
|
818 gsi_next (&gsi);
|
|
|
819 }
|
|
|
820 }
|
|
|
821
|
|
|
822 phi = phi_nodes (bb);
|
|
|
823 if (phi)
|
|
|
824 {
|
|
|
825 edge_iterator ei;
|
|
|
826 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
827 eliminate_phi (e, g);
|
|
|
828 }
|
|
|
829 }
|
|
|
830
|
|
|
831 delete_elim_graph (g);
|
|
|
832 }
|
|
|
833
|
|
|
834 /* These are the local work structures used to determine the best place to
|
|
|
835 insert the copies that were placed on edges by the SSA->normal pass.. */
|
|
|
836 static VEC(edge,heap) *edge_leader;
|
|
|
837 static VEC(gimple_seq,heap) *stmt_list;
|
|
|
838 static bitmap leader_has_match = NULL;
|
|
|
839 static edge leader_match = NULL;
|
|
|
840
|
|
|
841
|
|
|
842 /* Pass this function to make_forwarder_block so that all the edges with
|
|
|
843 matching PENDING_STMT lists to 'curr_stmt_list' get redirected. E is the
|
|
|
844 edge to test for a match. */
|
|
|
845
|
|
|
846 static inline bool
|
|
|
847 same_stmt_list_p (edge e)
|
|
|
848 {
|
|
|
849 return (e->aux == (PTR) leader_match) ? true : false;
|
|
|
850 }
|
|
|
851
|
|
|
852
|
|
|
853 /* Return TRUE if S1 and S2 are equivalent copies. */
|
|
|
854
|
|
|
855 static inline bool
|
|
|
856 identical_copies_p (const_gimple s1, const_gimple s2)
|
|
|
857 {
|
|
|
858 #ifdef ENABLE_CHECKING
|
|
|
859 gcc_assert (is_gimple_assign (s1));
|
|
|
860 gcc_assert (is_gimple_assign (s2));
|
|
|
861 gcc_assert (DECL_P (gimple_assign_lhs (s1)));
|
|
|
862 gcc_assert (DECL_P (gimple_assign_lhs (s2)));
|
|
|
863 #endif
|
|
|
864
|
|
|
865 if (gimple_assign_lhs (s1) != gimple_assign_lhs (s2))
|
|
|
866 return false;
|
|
|
867
|
|
|
868 if (gimple_assign_rhs1 (s1) != gimple_assign_rhs1 (s2))
|
|
|
869 return false;
|
|
|
870
|
|
|
871 return true;
|
|
|
872 }
|
|
|
873
|
|
|
874
|
|
|
875 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
|
|
|
876 contain the same sequence of copies. */
|
|
|
877
|
|
|
878 static inline bool
|
|
|
879 identical_stmt_lists_p (const_edge e1, const_edge e2)
|
|
|
880 {
|
|
|
881 gimple_seq t1 = PENDING_STMT (e1);
|
|
|
882 gimple_seq t2 = PENDING_STMT (e2);
|
|
|
883 gimple_stmt_iterator gsi1, gsi2;
|
|
|
884
|
|
|
885 for (gsi1 = gsi_start (t1), gsi2 = gsi_start (t2);
|
|
|
886 !gsi_end_p (gsi1) && !gsi_end_p (gsi2);
|
|
|
887 gsi_next (&gsi1), gsi_next (&gsi2))
|
|
|
888 {
|
|
|
889 if (!identical_copies_p (gsi_stmt (gsi1), gsi_stmt (gsi2)))
|
|
|
890 break;
|
|
|
891 }
|
|
|
892
|
|
|
893 if (!gsi_end_p (gsi1) || !gsi_end_p (gsi2))
|
|
|
894 return false;
|
|
|
895
|
|
|
896 return true;
|
|
|
897 }
|
|
|
898
|
|
|
899
|
|
|
900 /* Allocate data structures used in analyze_edges_for_bb. */
|
|
|
901
|
|
|
902 static void
|
|
|
903 init_analyze_edges_for_bb (void)
|
|
|
904 {
|
|
|
905 edge_leader = VEC_alloc (edge, heap, 25);
|
|
|
906 stmt_list = VEC_alloc (gimple_seq, heap, 25);
|
|
|
907 leader_has_match = BITMAP_ALLOC (NULL);
|
|
|
908 }
|
|
|
909
|
|
|
910
|
|
|
911 /* Free data structures used in analyze_edges_for_bb. */
|
|
|
912
|
|
|
913 static void
|
|
|
914 fini_analyze_edges_for_bb (void)
|
|
|
915 {
|
|
|
916 VEC_free (edge, heap, edge_leader);
|
|
|
917 VEC_free (gimple_seq, heap, stmt_list);
|
|
|
918 BITMAP_FREE (leader_has_match);
|
|
|
919 }
|
|
|
920
|
|
|
921 /* A helper function to be called via walk_tree. Return DATA if it is
|
|
|
922 contained in subtree TP. */
|
|
|
923
|
|
|
924 static tree
|
|
|
925 contains_tree_r (tree * tp, int *walk_subtrees, void *data)
|
|
|
926 {
|
|
|
927 if (*tp == data)
|
|
|
928 {
|
|
|
929 *walk_subtrees = 0;
|
|
|
930 return (tree) data;
|
|
|
931 }
|
|
|
932 else
|
|
|
933 return NULL_TREE;
|
|
|
934 }
|
|
|
935
|
|
|
936 /* A threshold for the number of insns contained in the latch block.
|
|
|
937 It is used to prevent blowing the loop with too many copies from
|
|
|
938 the latch. */
|
|
|
939 #define MAX_STMTS_IN_LATCH 2
|
|
|
940
|
|
|
941 /* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
|
|
|
942 body of the loop. This should be permitted only if SINGLE-EDGE is a
|
|
|
943 single-basic-block latch edge and thus cleaning the latch will help
|
|
|
944 to create a single-basic-block loop. Otherwise return FALSE. */
|
|
|
945
|
|
|
946 static bool
|
|
|
947 process_single_block_loop_latch (edge single_edge)
|
|
|
948 {
|
|
|
949 gimple_seq stmts;
|
|
|
950 basic_block b_exit, b_pheader, b_loop = single_edge->src;
|
|
|
951 edge_iterator ei;
|
|
|
952 edge e;
|
|
|
953 gimple_stmt_iterator gsi, gsi_exit;
|
|
|
954 gimple_stmt_iterator tsi;
|
|
|
955 tree expr;
|
|
|
956 gimple stmt;
|
|
|
957 unsigned int count = 0;
|
|
|
958
|
|
|
959 if (single_edge == NULL || (single_edge->dest != single_edge->src)
|
|
|
960 || (EDGE_COUNT (b_loop->succs) != 2)
|
|
|
961 || (EDGE_COUNT (b_loop->preds) != 2))
|
|
|
962 return false;
|
|
|
963
|
|
|
964 /* Get the stmts on the latch edge. */
|
|
|
965 stmts = PENDING_STMT (single_edge);
|
|
|
966
|
|
|
967 /* Find the successor edge which is not the latch edge. */
|
|
|
968 FOR_EACH_EDGE (e, ei, b_loop->succs)
|
|
|
969 if (e->dest != b_loop)
|
|
|
970 break;
|
|
|
971
|
|
|
972 b_exit = e->dest;
|
|
|
973
|
|
|
974 /* Check that the exit block has only the loop as a predecessor,
|
|
|
975 and that there are no pending stmts on that edge as well. */
|
|
|
976 if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
|
|
|
977 return false;
|
|
|
978
|
|
|
979 /* Find the predecessor edge which is not the latch edge. */
|
|
|
980 FOR_EACH_EDGE (e, ei, b_loop->preds)
|
|
|
981 if (e->src != b_loop)
|
|
|
982 break;
|
|
|
983
|
|
|
984 b_pheader = e->src;
|
|
|
985
|
|
|
986 if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop)
|
|
|
987 return false;
|
|
|
988
|
|
|
989 gsi_exit = gsi_after_labels (b_exit);
|
|
|
990
|
|
|
991 /* Get the last stmt in the loop body. */
|
|
|
992 gsi = gsi_last_bb (single_edge->src);
|
|
|
993 stmt = gsi_stmt (gsi);
|
|
|
994
|
|
|
995 if (gimple_code (stmt) != GIMPLE_COND)
|
|
|
996 return false;
|
|
|
997
|
|
|
998
|
|
|
999 expr = build2 (gimple_cond_code (stmt), boolean_type_node,
|
|
|
1000 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
|
|
|
1001 /* Iterate over the insns on the latch and count them. */
|
|
|
1002 for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
|
|
|
1003 {
|
|
|
1004 gimple stmt1 = gsi_stmt (tsi);
|
|
|
1005 tree var;
|
|
|
1006
|
|
|
1007 count++;
|
|
|
1008 /* Check that the condition does not contain any new definition
|
|
|
1009 created in the latch as the stmts from the latch intended
|
|
|
1010 to precede it. */
|
|
|
1011 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
|
|
|
1012 return false;
|
|
|
1013 var = gimple_assign_lhs (stmt1);
|
|
|
1014 if (TREE_THIS_VOLATILE (var)
|
|
|
1015 || TYPE_VOLATILE (TREE_TYPE (var))
|
|
|
1016 || walk_tree (&expr, contains_tree_r, var, NULL))
|
|
|
1017 return false;
|
|
|
1018 }
|
|
|
1019 /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
|
|
|
1020 insns. The purpose of this restriction is to prevent blowing the
|
|
|
1021 loop with too many copies from the latch. */
|
|
|
1022 if (count > MAX_STMTS_IN_LATCH)
|
|
|
1023 return false;
|
|
|
1024
|
|
|
1025 /* Apply the transformation - clean up the latch block:
|
|
|
1026
|
|
|
1027 var = something;
|
|
|
1028 L1:
|
|
|
1029 x1 = expr;
|
|
|
1030 if (cond) goto L2 else goto L3;
|
|
|
1031 L2:
|
|
|
1032 var = x1;
|
|
|
1033 goto L1
|
|
|
1034 L3:
|
|
|
1035 ...
|
|
|
1036
|
|
|
1037 ==>
|
|
|
1038
|
|
|
1039 var = something;
|
|
|
1040 L1:
|
|
|
1041 x1 = expr;
|
|
|
1042 tmp_var = var;
|
|
|
1043 var = x1;
|
|
|
1044 if (cond) goto L1 else goto L2;
|
|
|
1045 L2:
|
|
|
1046 var = tmp_var;
|
|
|
1047 ...
|
|
|
1048 */
|
|
|
1049 for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
|
|
|
1050 {
|
|
|
1051 gimple stmt1 = gsi_stmt (tsi);
|
|
|
1052 tree var, tmp_var;
|
|
|
1053 gimple copy;
|
|
|
1054
|
|
|
1055 /* Create a new variable to load back the value of var in case
|
|
|
1056 we exit the loop. */
|
|
|
1057 var = gimple_assign_lhs (stmt1);
|
|
|
1058 tmp_var = create_temp (var);
|
|
|
1059 copy = gimple_build_assign (tmp_var, var);
|
|
|
1060 set_is_used (tmp_var);
|
|
|
1061 gsi_insert_before (&gsi, copy, GSI_SAME_STMT);
|
|
|
1062 copy = gimple_build_assign (var, tmp_var);
|
|
|
1063 gsi_insert_before (&gsi_exit, copy, GSI_SAME_STMT);
|
|
|
1064 }
|
|
|
1065
|
|
|
1066 PENDING_STMT (single_edge) = 0;
|
|
|
1067 /* Insert the new stmts to the loop body. */
|
|
|
1068 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
|
|
|
1069
|
|
|
1070 if (dump_file)
|
|
|
1071 fprintf (dump_file,
|
|
|
1072 "\nCleaned-up latch block of loop with single BB: %d\n\n",
|
|
|
1073 single_edge->dest->index);
|
|
|
1074
|
|
|
1075 return true;
|
|
|
1076 }
|
|
|
1077
|
|
|
1078 /* Look at all the incoming edges to block BB, and decide where the best place
|
|
|
1079 to insert the stmts on each edge are, and perform those insertions. */
|
|
|
1080
|
|
|
1081 static void
|
|
|
1082 analyze_edges_for_bb (basic_block bb)
|
|
|
1083 {
|
|
|
1084 edge e;
|
|
|
1085 edge_iterator ei;
|
|
|
1086 int count;
|
|
|
1087 unsigned int x;
|
|
|
1088 bool have_opportunity;
|
|
|
1089 gimple_stmt_iterator gsi;
|
|
|
1090 gimple stmt;
|
|
|
1091 edge single_edge = NULL;
|
|
|
1092 bool is_label;
|
|
|
1093 edge leader;
|
|
|
1094
|
|
|
1095 count = 0;
|
|
|
1096
|
|
|
1097 /* Blocks which contain at least one abnormal edge cannot use
|
|
|
1098 make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
|
|
|
1099 found on edges in these block. */
|
|
|
1100 have_opportunity = true;
|
|
|
1101 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1102 if (e->flags & EDGE_ABNORMAL)
|
|
|
1103 {
|
|
|
1104 have_opportunity = false;
|
|
|
1105 break;
|
|
|
1106 }
|
|
|
1107
|
|
|
1108 if (!have_opportunity)
|
|
|
1109 {
|
|
|
1110 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1111 if (PENDING_STMT (e))
|
|
|
1112 gsi_commit_one_edge_insert (e, NULL);
|
|
|
1113 return;
|
|
|
1114 }
|
|
|
1115
|
|
|
1116 /* Find out how many edges there are with interesting pending stmts on them.
|
|
|
1117 Commit the stmts on edges we are not interested in. */
|
|
|
1118 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1119 {
|
|
|
1120 if (PENDING_STMT (e))
|
|
|
1121 {
|
|
|
1122 gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
|
|
1123 if (e->flags & EDGE_FALLTHRU)
|
|
|
1124 {
|
|
|
1125 gsi = gsi_start_bb (e->src);
|
|
|
1126 if (!gsi_end_p (gsi))
|
|
|
1127 {
|
|
|
1128 stmt = gsi_stmt (gsi);
|
|
|
1129 gsi_next (&gsi);
|
|
|
1130 gcc_assert (stmt != NULL);
|
|
|
1131 is_label = (gimple_code (stmt) == GIMPLE_LABEL);
|
|
|
1132 /* Punt if it has non-label stmts, or isn't local. */
|
|
|
1133 if (!is_label
|
|
|
1134 || DECL_NONLOCAL (gimple_label_label (stmt))
|
|
|
1135 || !gsi_end_p (gsi))
|
|
|
1136 {
|
|
|
1137 gsi_commit_one_edge_insert (e, NULL);
|
|
|
1138 continue;
|
|
|
1139 }
|
|
|
1140 }
|
|
|
1141 }
|
|
|
1142 single_edge = e;
|
|
|
1143 count++;
|
|
|
1144 }
|
|
|
1145 }
|
|
|
1146
|
|
|
1147 /* If there aren't at least 2 edges, no sharing will happen. */
|
|
|
1148 if (count < 2)
|
|
|
1149 {
|
|
|
1150 if (single_edge)
|
|
|
1151 {
|
|
|
1152 /* Add stmts to the edge unless processed specially as a
|
|
|
1153 single-block loop latch edge. */
|
|
|
1154 if (!process_single_block_loop_latch (single_edge))
|
|
|
1155 gsi_commit_one_edge_insert (single_edge, NULL);
|
|
|
1156 }
|
|
|
1157 return;
|
|
|
1158 }
|
|
|
1159
|
|
|
1160 /* Ensure that we have empty worklists. */
|
|
|
1161 #ifdef ENABLE_CHECKING
|
|
|
1162 gcc_assert (VEC_length (edge, edge_leader) == 0);
|
|
|
1163 gcc_assert (VEC_length (gimple_seq, stmt_list) == 0);
|
|
|
1164 gcc_assert (bitmap_empty_p (leader_has_match));
|
|
|
1165 #endif
|
|
|
1166
|
|
|
1167 /* Find the "leader" block for each set of unique stmt lists. Preference is
|
|
|
1168 given to FALLTHRU blocks since they would need a GOTO to arrive at another
|
|
|
1169 block. The leader edge destination is the block which all the other edges
|
|
|
1170 with the same stmt list will be redirected to. */
|
|
|
1171 have_opportunity = false;
|
|
|
1172 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1173 {
|
|
|
1174 if (PENDING_STMT (e))
|
|
|
1175 {
|
|
|
1176 bool found = false;
|
|
|
1177
|
|
|
1178 /* Look for the same stmt list in edge leaders list. */
|
|
|
1179 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
|
|
|
1180 {
|
|
|
1181 if (identical_stmt_lists_p (leader, e))
|
|
|
1182 {
|
|
|
1183 /* Give this edge the same stmt list pointer. */
|
|
|
1184 PENDING_STMT (e) = NULL;
|
|
|
1185 e->aux = leader;
|
|
|
1186 bitmap_set_bit (leader_has_match, x);
|
|
|
1187 have_opportunity = found = true;
|
|
|
1188 break;
|
|
|
1189 }
|
|
|
1190 }
|
|
|
1191
|
|
|
1192 /* If no similar stmt list, add this edge to the leader list. */
|
|
|
1193 if (!found)
|
|
|
1194 {
|
|
|
1195 VEC_safe_push (edge, heap, edge_leader, e);
|
|
|
1196 VEC_safe_push (gimple_seq, heap, stmt_list, PENDING_STMT (e));
|
|
|
1197 }
|
|
|
1198 }
|
|
|
1199 }
|
|
|
1200
|
|
|
1201 /* If there are no similar lists, just issue the stmts. */
|
|
|
1202 if (!have_opportunity)
|
|
|
1203 {
|
|
|
1204 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
|
|
|
1205 gsi_commit_one_edge_insert (leader, NULL);
|
|
|
1206 VEC_truncate (edge, edge_leader, 0);
|
|
|
1207 VEC_truncate (gimple_seq, stmt_list, 0);
|
|
|
1208 bitmap_clear (leader_has_match);
|
|
|
1209 return;
|
|
|
1210 }
|
|
|
1211
|
|
|
1212 if (dump_file)
|
|
|
1213 fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
|
|
|
1214 bb->index);
|
|
|
1215
|
|
|
1216 /* For each common list, create a forwarding block and issue the stmt's
|
|
|
1217 in that block. */
|
|
|
1218 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
|
|
|
1219 if (bitmap_bit_p (leader_has_match, x))
|
|
|
1220 {
|
|
|
1221 edge new_edge;
|
|
|
1222 gimple_stmt_iterator gsi;
|
|
|
1223 gimple_seq curr_stmt_list;
|
|
|
1224
|
|
|
1225 leader_match = leader;
|
|
|
1226
|
|
|
1227 /* The tree_* cfg manipulation routines use the PENDING_EDGE field
|
|
|
1228 for various PHI manipulations, so it gets cleared when calls are
|
|
|
1229 made to make_forwarder_block(). So make sure the edge is clear,
|
|
|
1230 and use the saved stmt list. */
|
|
|
1231 PENDING_STMT (leader) = NULL;
|
|
|
1232 leader->aux = leader;
|
|
|
1233 curr_stmt_list = VEC_index (gimple_seq, stmt_list, x);
|
|
|
1234
|
|
|
1235 new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
|
|
|
1236 NULL);
|
|
|
1237 bb = new_edge->dest;
|
|
|
1238 if (dump_file)
|
|
|
1239 {
|
|
|
1240 fprintf (dump_file, "Splitting BB %d for Common stmt list. ",
|
|
|
1241 leader->dest->index);
|
|
|
1242 fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
|
|
|
1243 print_gimple_seq (dump_file, curr_stmt_list, 0, TDF_VOPS);
|
|
|
1244 }
|
|
|
1245
|
|
|
1246 FOR_EACH_EDGE (e, ei, new_edge->src->preds)
|
|
|
1247 {
|
|
|
1248 e->aux = NULL;
|
|
|
1249 if (dump_file)
|
|
|
1250 fprintf (dump_file, " Edge (%d->%d) lands here.\n",
|
|
|
1251 e->src->index, e->dest->index);
|
|
|
1252 }
|
|
|
1253
|
|
|
1254 gsi = gsi_last_bb (leader->dest);
|
|
|
1255 gsi_insert_seq_after (&gsi, curr_stmt_list, GSI_NEW_STMT);
|
|
|
1256
|
|
|
1257 leader_match = NULL;
|
|
|
1258 /* We should never get a new block now. */
|
|
|
1259 }
|
|
|
1260 else
|
|
|
1261 {
|
|
|
1262 PENDING_STMT (leader) = VEC_index (gimple_seq, stmt_list, x);
|
|
|
1263 gsi_commit_one_edge_insert (leader, NULL);
|
|
|
1264 }
|
|
|
1265
|
|
|
1266
|
|
|
1267 /* Clear the working data structures. */
|
|
|
1268 VEC_truncate (edge, edge_leader, 0);
|
|
|
1269 VEC_truncate (gimple_seq, stmt_list, 0);
|
|
|
1270 bitmap_clear (leader_has_match);
|
|
|
1271 }
|
|
|
1272
|
|
|
1273
|
|
|
1274 /* This function will analyze the insertions which were performed on edges,
|
|
|
1275 and decide whether they should be left on that edge, or whether it is more
|
|
|
1276 efficient to emit some subset of them in a single block. All stmts are
|
|
|
1277 inserted somewhere. */
|
|
|
1278
|
|
|
1279 static void
|
|
|
1280 perform_edge_inserts (void)
|
|
|
1281 {
|
|
|
1282 basic_block bb;
|
|
|
1283
|
|
|
1284 if (dump_file)
|
|
|
1285 fprintf(dump_file, "Analyzing Edge Insertions.\n");
|
|
|
1286
|
|
|
1287 /* analyze_edges_for_bb calls make_forwarder_block, which tries to
|
|
|
1288 incrementally update the dominator information. Since we don't
|
|
|
1289 need dominator information after this pass, go ahead and free the
|
|
|
1290 dominator information. */
|
|
|
1291 free_dominance_info (CDI_DOMINATORS);
|
|
|
1292 free_dominance_info (CDI_POST_DOMINATORS);
|
|
|
1293
|
|
|
1294 /* Allocate data structures used in analyze_edges_for_bb. */
|
|
|
1295 init_analyze_edges_for_bb ();
|
|
|
1296
|
|
|
1297 FOR_EACH_BB (bb)
|
|
|
1298 analyze_edges_for_bb (bb);
|
|
|
1299
|
|
|
1300 analyze_edges_for_bb (EXIT_BLOCK_PTR);
|
|
|
1301
|
|
|
1302 /* Free data structures used in analyze_edges_for_bb. */
|
|
|
1303 fini_analyze_edges_for_bb ();
|
|
|
1304
|
|
|
1305 #ifdef ENABLE_CHECKING
|
|
|
1306 {
|
|
|
1307 edge_iterator ei;
|
|
|
1308 edge e;
|
|
|
1309 FOR_EACH_BB (bb)
|
|
|
1310 {
|
|
|
1311 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1312 {
|
|
|
1313 if (PENDING_STMT (e))
|
|
|
1314 error (" Pending stmts not issued on PRED edge (%d, %d)\n",
|
|
|
1315 e->src->index, e->dest->index);
|
|
|
1316 }
|
|
|
1317 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1318 {
|
|
|
1319 if (PENDING_STMT (e))
|
|
|
1320 error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
|
|
|
1321 e->src->index, e->dest->index);
|
|
|
1322 }
|
|
|
1323 }
|
|
|
1324 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
|
|
1325 {
|
|
|
1326 if (PENDING_STMT (e))
|
|
|
1327 error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
|
|
|
1328 e->src->index, e->dest->index);
|
|
|
1329 }
|
|
|
1330 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
1331 {
|
|
|
1332 if (PENDING_STMT (e))
|
|
|
1333 error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
|
|
|
1334 e->src->index, e->dest->index);
|
|
|
1335 }
|
|
|
1336 }
|
|
|
1337 #endif
|
|
|
1338 }
|
|
|
1339
|
|
|
1340
|
|
|
1341 /* Remove the ssa-names in the current function and translate them into normal
|
|
|
1342 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
|
|
|
1343 should also be used. */
|
|
|
1344
|
|
|
1345 static void
|
|
|
1346 remove_ssa_form (bool perform_ter)
|
|
|
1347 {
|
|
|
1348 basic_block bb;
|
|
|
1349 gimple *values = NULL;
|
|
|
1350 var_map map;
|
|
|
1351 gimple_stmt_iterator gsi;
|
|
|
1352
|
|
|
1353 map = coalesce_ssa_name ();
|
|
|
1354
|
|
|
1355 /* Return to viewing the variable list as just all reference variables after
|
|
|
1356 coalescing has been performed. */
|
|
|
1357 partition_view_normal (map, false);
|
|
|
1358
|
|
|
1359 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1360 {
|
|
|
1361 fprintf (dump_file, "After Coalescing:\n");
|
|
|
1362 dump_var_map (dump_file, map);
|
|
|
1363 }
|
|
|
1364
|
|
|
1365 if (perform_ter)
|
|
|
1366 {
|
|
|
1367 values = find_replaceable_exprs (map);
|
|
|
1368 if (values && dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1369 dump_replaceable_exprs (dump_file, values);
|
|
|
1370 }
|
|
|
1371
|
|
|
1372 /* Assign real variables to the partitions now. */
|
|
|
1373 assign_vars (map);
|
|
|
1374
|
|
|
1375 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1376 {
|
|
|
1377 fprintf (dump_file, "After Base variable replacement:\n");
|
|
|
1378 dump_var_map (dump_file, map);
|
|
|
1379 }
|
|
|
1380
|
|
|
1381 rewrite_trees (map, values);
|
|
|
1382
|
|
|
1383 if (values)
|
|
|
1384 free (values);
|
|
|
1385
|
|
|
1386 /* Remove PHI nodes which have been translated back to real variables. */
|
|
|
1387 FOR_EACH_BB (bb)
|
|
|
1388 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
|
|
|
1389 remove_phi_node (&gsi, true);
|
|
|
1390
|
|
|
1391 /* If any copies were inserted on edges, analyze and insert them now. */
|
|
|
1392 perform_edge_inserts ();
|
|
|
1393
|
|
|
1394 delete_var_map (map);
|
|
|
1395 }
|
|
|
1396
|
|
|
1397
|
|
|
1398 /* Search every PHI node for arguments associated with backedges which
|
|
|
1399 we can trivially determine will need a copy (the argument is either
|
|
|
1400 not an SSA_NAME or the argument has a different underlying variable
|
|
|
1401 than the PHI result).
|
|
|
1402
|
|
|
1403 Insert a copy from the PHI argument to a new destination at the
|
|
|
1404 end of the block with the backedge to the top of the loop. Update
|
|
|
1405 the PHI argument to reference this new destination. */
|
|
|
1406
|
|
|
1407 static void
|
|
|
1408 insert_backedge_copies (void)
|
|
|
1409 {
|
|
|
1410 basic_block bb;
|
|
|
1411 gimple_stmt_iterator gsi;
|
|
|
1412
|
|
|
1413 FOR_EACH_BB (bb)
|
|
|
1414 {
|
|
|
1415 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1416 {
|
|
|
1417 gimple phi = gsi_stmt (gsi);
|
|
|
1418 tree result = gimple_phi_result (phi);
|
|
|
1419 tree result_var;
|
|
|
1420 size_t i;
|
|
|
1421
|
|
|
1422 if (!is_gimple_reg (result))
|
|
|
1423 continue;
|
|
|
1424
|
|
|
1425 result_var = SSA_NAME_VAR (result);
|
|
|
1426 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
1427 {
|
|
|
1428 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
1429 edge e = gimple_phi_arg_edge (phi, i);
|
|
|
1430
|
|
|
1431 /* If the argument is not an SSA_NAME, then we will need a
|
|
|
1432 constant initialization. If the argument is an SSA_NAME with
|
|
|
1433 a different underlying variable then a copy statement will be
|
|
|
1434 needed. */
|
|
|
1435 if ((e->flags & EDGE_DFS_BACK)
|
|
|
1436 && (TREE_CODE (arg) != SSA_NAME
|
|
|
1437 || SSA_NAME_VAR (arg) != result_var))
|
|
|
1438 {
|
|
|
1439 tree name;
|
|
|
1440 gimple stmt, last = NULL;
|
|
|
1441 gimple_stmt_iterator gsi2;
|
|
|
1442
|
|
|
1443 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
|
|
|
1444 if (!gsi_end_p (gsi2))
|
|
|
1445 last = gsi_stmt (gsi2);
|
|
|
1446
|
|
|
1447 /* In theory the only way we ought to get back to the
|
|
|
1448 start of a loop should be with a COND_EXPR or GOTO_EXPR.
|
|
|
1449 However, better safe than sorry.
|
|
|
1450 If the block ends with a control statement or
|
|
|
1451 something that might throw, then we have to
|
|
|
1452 insert this assignment before the last
|
|
|
1453 statement. Else insert it after the last statement. */
|
|
|
1454 if (last && stmt_ends_bb_p (last))
|
|
|
1455 {
|
|
|
1456 /* If the last statement in the block is the definition
|
|
|
1457 site of the PHI argument, then we can't insert
|
|
|
1458 anything after it. */
|
|
|
1459 if (TREE_CODE (arg) == SSA_NAME
|
|
|
1460 && SSA_NAME_DEF_STMT (arg) == last)
|
|
|
1461 continue;
|
|
|
1462 }
|
|
|
1463
|
|
|
1464 /* Create a new instance of the underlying variable of the
|
|
|
1465 PHI result. */
|
|
|
1466 stmt = gimple_build_assign (result_var,
|
|
|
1467 gimple_phi_arg_def (phi, i));
|
|
|
1468 name = make_ssa_name (result_var, stmt);
|
|
|
1469 gimple_assign_set_lhs (stmt, name);
|
|
|
1470
|
|
|
1471 /* Insert the new statement into the block and update
|
|
|
1472 the PHI node. */
|
|
|
1473 if (last && stmt_ends_bb_p (last))
|
|
|
1474 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
|
|
|
1475 else
|
|
|
1476 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
|
|
|
1477 SET_PHI_ARG_DEF (phi, i, name);
|
|
|
1478 }
|
|
|
1479 }
|
|
|
1480 }
|
|
|
1481 }
|
|
|
1482 }
|
|
|
1483
|
|
|
1484 /* Take the current function out of SSA form, translating PHIs as described in
|
|
|
1485 R. Morgan, ``Building an Optimizing Compiler'',
|
|
|
1486 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
|
|
|
1487
|
|
|
1488 static unsigned int
|
|
|
1489 rewrite_out_of_ssa (void)
|
|
|
1490 {
|
|
|
1491 /* If elimination of a PHI requires inserting a copy on a backedge,
|
|
|
1492 then we will have to split the backedge which has numerous
|
|
|
1493 undesirable performance effects.
|
|
|
1494
|
|
|
1495 A significant number of such cases can be handled here by inserting
|
|
|
1496 copies into the loop itself. */
|
|
|
1497 insert_backedge_copies ();
|
|
|
1498
|
|
|
1499
|
|
|
1500 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
|
|
|
1501 eliminate_useless_phis ();
|
|
|
1502
|
|
|
1503 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1504 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
|
|
|
1505
|
|
|
1506 remove_ssa_form (flag_tree_ter && !flag_mudflap);
|
|
|
1507
|
|
|
1508 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1509 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
|
|
|
1510
|
|
|
1511 cfun->gimple_df->in_ssa_p = false;
|
|
|
1512 return 0;
|
|
|
1513 }
|
|
|
1514
|
|
|
1515
|
|
|
1516 /* Define the parameters of the out of SSA pass. */
|
|
|
1517
|
|
|
1518 struct gimple_opt_pass pass_del_ssa =
|
|
|
1519 {
|
|
|
1520 {
|
|
|
1521 GIMPLE_PASS,
|
|
|
1522 "optimized", /* name */
|
|
|
1523 NULL, /* gate */
|
|
|
1524 rewrite_out_of_ssa, /* execute */
|
|
|
1525 NULL, /* sub */
|
|
|
1526 NULL, /* next */
|
|
|
1527 0, /* static_pass_number */
|
|
|
1528 TV_TREE_SSA_TO_NORMAL, /* tv_id */
|
|
|
1529 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
1530 0, /* properties_provided */
|
|
|
1531 /* ??? If TER is enabled, we also kill gimple. */
|
|
|
1532 PROP_ssa, /* properties_destroyed */
|
|
|
1533 TODO_verify_ssa | TODO_verify_flow
|
|
|
1534 | TODO_verify_stmts, /* todo_flags_start */
|
|
|
1535 TODO_dump_func
|
|
|
1536 | TODO_ggc_collect
|
|
|
1537 | TODO_remove_unused_locals /* todo_flags_finish */
|
|
|
1538 }
|
|
|
1539 };
|
