Mercurial > hg > CbC > CbC_gcc
annotate gcc/lcm.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 22 Mar 2011 17:18:12 +0900 |
parents | b7f97abdc517 |
children | 04ced10e8804 |
rev | line source |
---|---|
0 | 1 /* Generic partial redundancy elimination with lazy code motion support. |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3 2010, 2011 Free Software Foundation, Inc. |
0 | 4 |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify it under | |
8 the terms of the GNU General Public License as published by the Free | |
9 Software Foundation; either version 3, or (at your option) any later | |
10 version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 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 /* These routines are meant to be used by various optimization | |
22 passes which can be modeled as lazy code motion problems. | |
23 Including, but not limited to: | |
24 | |
25 * Traditional partial redundancy elimination. | |
26 | |
27 * Placement of caller/caller register save/restores. | |
28 | |
29 * Load/store motion. | |
30 | |
31 * Copy motion. | |
32 | |
33 * Conversion of flat register files to a stacked register | |
34 model. | |
35 | |
36 * Dead load/store elimination. | |
37 | |
38 These routines accept as input: | |
39 | |
40 * Basic block information (number of blocks, lists of | |
41 predecessors and successors). Note the granularity | |
42 does not need to be basic block, they could be statements | |
43 or functions. | |
44 | |
45 * Bitmaps of local properties (computed, transparent and | |
46 anticipatable expressions). | |
47 | |
48 The output of these routines is bitmap of redundant computations | |
49 and a bitmap of optimal placement points. */ | |
50 | |
51 | |
52 #include "config.h" | |
53 #include "system.h" | |
54 #include "coretypes.h" | |
55 #include "tm.h" | |
56 #include "rtl.h" | |
57 #include "regs.h" | |
58 #include "hard-reg-set.h" | |
59 #include "flags.h" | |
60 #include "insn-config.h" | |
61 #include "recog.h" | |
62 #include "basic-block.h" | |
63 #include "output.h" | |
64 #include "tm_p.h" | |
65 #include "function.h" | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
66 #include "sbitmap.h" |
0 | 67 |
68 /* We want target macros for the mode switching code to be able to refer | |
69 to instruction attribute values. */ | |
70 #include "insn-attr.h" | |
71 | |
72 /* Edge based LCM routines. */ | |
73 static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *); | |
74 static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *, | |
75 sbitmap *, sbitmap *, sbitmap *); | |
76 static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *, | |
77 sbitmap *, sbitmap *); | |
78 static void compute_insert_delete (struct edge_list *edge_list, sbitmap *, | |
79 sbitmap *, sbitmap *, sbitmap *, sbitmap *); | |
80 | |
81 /* Edge based LCM routines on a reverse flowgraph. */ | |
82 static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *, | |
83 sbitmap*, sbitmap *, sbitmap *); | |
84 static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *, | |
85 sbitmap *, sbitmap *); | |
86 static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *, | |
87 sbitmap *, sbitmap *, sbitmap *, | |
88 sbitmap *); | |
89 | |
90 /* Edge based lcm routines. */ | |
91 | |
92 /* Compute expression anticipatability at entrance and exit of each block. | |
93 This is done based on the flow graph, and not on the pred-succ lists. | |
94 Other than that, its pretty much identical to compute_antinout. */ | |
95 | |
96 static void | |
97 compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, | |
98 sbitmap *antout) | |
99 { | |
100 basic_block bb; | |
101 edge e; | |
102 basic_block *worklist, *qin, *qout, *qend; | |
103 unsigned int qlen; | |
104 edge_iterator ei; | |
105 | |
106 /* Allocate a worklist array/queue. Entries are only added to the | |
107 list if they were not already on the list. So the size is | |
108 bounded by the number of basic blocks. */ | |
109 qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks); | |
110 | |
111 /* We want a maximal solution, so make an optimistic initialization of | |
112 ANTIN. */ | |
113 sbitmap_vector_ones (antin, last_basic_block); | |
114 | |
115 /* Put every block on the worklist; this is necessary because of the | |
116 optimistic initialization of ANTIN above. */ | |
117 FOR_EACH_BB_REVERSE (bb) | |
118 { | |
119 *qin++ = bb; | |
120 bb->aux = bb; | |
121 } | |
122 | |
123 qin = worklist; | |
124 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; | |
125 qlen = n_basic_blocks - NUM_FIXED_BLOCKS; | |
126 | |
127 /* Mark blocks which are predecessors of the exit block so that we | |
128 can easily identify them below. */ | |
129 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) | |
130 e->src->aux = EXIT_BLOCK_PTR; | |
131 | |
132 /* Iterate until the worklist is empty. */ | |
133 while (qlen) | |
134 { | |
135 /* Take the first entry off the worklist. */ | |
136 bb = *qout++; | |
137 qlen--; | |
138 | |
139 if (qout >= qend) | |
140 qout = worklist; | |
141 | |
142 if (bb->aux == EXIT_BLOCK_PTR) | |
143 /* Do not clear the aux field for blocks which are predecessors of | |
144 the EXIT block. That way we never add then to the worklist | |
145 again. */ | |
146 sbitmap_zero (antout[bb->index]); | |
147 else | |
148 { | |
149 /* Clear the aux field of this block so that it can be added to | |
150 the worklist again if necessary. */ | |
151 bb->aux = NULL; | |
152 sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index); | |
153 } | |
154 | |
155 if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index], | |
156 transp[bb->index], antout[bb->index])) | |
157 /* If the in state of this block changed, then we need | |
158 to add the predecessors of this block to the worklist | |
159 if they are not already on the worklist. */ | |
160 FOR_EACH_EDGE (e, ei, bb->preds) | |
161 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) | |
162 { | |
163 *qin++ = e->src; | |
164 e->src->aux = e; | |
165 qlen++; | |
166 if (qin >= qend) | |
167 qin = worklist; | |
168 } | |
169 } | |
170 | |
171 clear_aux_for_edges (); | |
172 clear_aux_for_blocks (); | |
173 free (worklist); | |
174 } | |
175 | |
176 /* Compute the earliest vector for edge based lcm. */ | |
177 | |
178 static void | |
179 compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, | |
180 sbitmap *antout, sbitmap *avout, sbitmap *kill, | |
181 sbitmap *earliest) | |
182 { | |
183 sbitmap difference, temp_bitmap; | |
184 int x, num_edges; | |
185 basic_block pred, succ; | |
186 | |
187 num_edges = NUM_EDGES (edge_list); | |
188 | |
189 difference = sbitmap_alloc (n_exprs); | |
190 temp_bitmap = sbitmap_alloc (n_exprs); | |
191 | |
192 for (x = 0; x < num_edges; x++) | |
193 { | |
194 pred = INDEX_EDGE_PRED_BB (edge_list, x); | |
195 succ = INDEX_EDGE_SUCC_BB (edge_list, x); | |
196 if (pred == ENTRY_BLOCK_PTR) | |
197 sbitmap_copy (earliest[x], antin[succ->index]); | |
198 else | |
199 { | |
200 if (succ == EXIT_BLOCK_PTR) | |
201 sbitmap_zero (earliest[x]); | |
202 else | |
203 { | |
204 sbitmap_difference (difference, antin[succ->index], | |
205 avout[pred->index]); | |
206 sbitmap_not (temp_bitmap, antout[pred->index]); | |
207 sbitmap_a_and_b_or_c (earliest[x], difference, | |
208 kill[pred->index], temp_bitmap); | |
209 } | |
210 } | |
211 } | |
212 | |
213 sbitmap_free (temp_bitmap); | |
214 sbitmap_free (difference); | |
215 } | |
216 | |
217 /* later(p,s) is dependent on the calculation of laterin(p). | |
218 laterin(p) is dependent on the calculation of later(p2,p). | |
219 | |
220 laterin(ENTRY) is defined as all 0's | |
221 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY) | |
222 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)). | |
223 | |
224 If we progress in this manner, starting with all basic blocks | |
225 in the work list, anytime we change later(bb), we need to add | |
226 succs(bb) to the worklist if they are not already on the worklist. | |
227 | |
228 Boundary conditions: | |
229 | |
230 We prime the worklist all the normal basic blocks. The ENTRY block can | |
231 never be added to the worklist since it is never the successor of any | |
232 block. We explicitly prevent the EXIT block from being added to the | |
233 worklist. | |
234 | |
235 We optimistically initialize LATER. That is the only time this routine | |
236 will compute LATER for an edge out of the entry block since the entry | |
237 block is never on the worklist. Thus, LATERIN is neither used nor | |
238 computed for the ENTRY block. | |
239 | |
240 Since the EXIT block is never added to the worklist, we will neither | |
241 use nor compute LATERIN for the exit block. Edges which reach the | |
242 EXIT block are handled in the normal fashion inside the loop. However, | |
243 the insertion/deletion computation needs LATERIN(EXIT), so we have | |
244 to compute it. */ | |
245 | |
246 static void | |
247 compute_laterin (struct edge_list *edge_list, sbitmap *earliest, | |
248 sbitmap *antloc, sbitmap *later, sbitmap *laterin) | |
249 { | |
250 int num_edges, i; | |
251 edge e; | |
252 basic_block *worklist, *qin, *qout, *qend, bb; | |
253 unsigned int qlen; | |
254 edge_iterator ei; | |
255 | |
256 num_edges = NUM_EDGES (edge_list); | |
257 | |
258 /* Allocate a worklist array/queue. Entries are only added to the | |
259 list if they were not already on the list. So the size is | |
260 bounded by the number of basic blocks. */ | |
261 qin = qout = worklist | |
262 = XNEWVEC (basic_block, n_basic_blocks); | |
263 | |
264 /* Initialize a mapping from each edge to its index. */ | |
265 for (i = 0; i < num_edges; i++) | |
266 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; | |
267 | |
268 /* We want a maximal solution, so initially consider LATER true for | |
269 all edges. This allows propagation through a loop since the incoming | |
270 loop edge will have LATER set, so if all the other incoming edges | |
271 to the loop are set, then LATERIN will be set for the head of the | |
272 loop. | |
273 | |
274 If the optimistic setting of LATER on that edge was incorrect (for | |
275 example the expression is ANTLOC in a block within the loop) then | |
276 this algorithm will detect it when we process the block at the head | |
277 of the optimistic edge. That will requeue the affected blocks. */ | |
278 sbitmap_vector_ones (later, num_edges); | |
279 | |
280 /* Note that even though we want an optimistic setting of LATER, we | |
281 do not want to be overly optimistic. Consider an outgoing edge from | |
282 the entry block. That edge should always have a LATER value the | |
283 same as EARLIEST for that edge. */ | |
284 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) | |
285 sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]); | |
286 | |
287 /* Add all the blocks to the worklist. This prevents an early exit from | |
288 the loop given our optimistic initialization of LATER above. */ | |
289 FOR_EACH_BB (bb) | |
290 { | |
291 *qin++ = bb; | |
292 bb->aux = bb; | |
293 } | |
294 | |
295 /* Note that we do not use the last allocated element for our queue, | |
296 as EXIT_BLOCK is never inserted into it. */ | |
297 qin = worklist; | |
298 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; | |
299 qlen = n_basic_blocks - NUM_FIXED_BLOCKS; | |
300 | |
301 /* Iterate until the worklist is empty. */ | |
302 while (qlen) | |
303 { | |
304 /* Take the first entry off the worklist. */ | |
305 bb = *qout++; | |
306 bb->aux = NULL; | |
307 qlen--; | |
308 if (qout >= qend) | |
309 qout = worklist; | |
310 | |
311 /* Compute the intersection of LATERIN for each incoming edge to B. */ | |
312 sbitmap_ones (laterin[bb->index]); | |
313 FOR_EACH_EDGE (e, ei, bb->preds) | |
314 sbitmap_a_and_b (laterin[bb->index], laterin[bb->index], | |
315 later[(size_t)e->aux]); | |
316 | |
317 /* Calculate LATER for all outgoing edges. */ | |
318 FOR_EACH_EDGE (e, ei, bb->succs) | |
319 if (sbitmap_union_of_diff_cg (later[(size_t) e->aux], | |
320 earliest[(size_t) e->aux], | |
321 laterin[e->src->index], | |
322 antloc[e->src->index]) | |
323 /* If LATER for an outgoing edge was changed, then we need | |
324 to add the target of the outgoing edge to the worklist. */ | |
325 && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0) | |
326 { | |
327 *qin++ = e->dest; | |
328 e->dest->aux = e; | |
329 qlen++; | |
330 if (qin >= qend) | |
331 qin = worklist; | |
332 } | |
333 } | |
334 | |
335 /* Computation of insertion and deletion points requires computing LATERIN | |
336 for the EXIT block. We allocated an extra entry in the LATERIN array | |
337 for just this purpose. */ | |
338 sbitmap_ones (laterin[last_basic_block]); | |
339 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) | |
340 sbitmap_a_and_b (laterin[last_basic_block], | |
341 laterin[last_basic_block], | |
342 later[(size_t) e->aux]); | |
343 | |
344 clear_aux_for_edges (); | |
345 free (worklist); | |
346 } | |
347 | |
348 /* Compute the insertion and deletion points for edge based LCM. */ | |
349 | |
350 static void | |
351 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, | |
352 sbitmap *later, sbitmap *laterin, sbitmap *insert, | |
353 sbitmap *del) | |
354 { | |
355 int x; | |
356 basic_block bb; | |
357 | |
358 FOR_EACH_BB (bb) | |
359 sbitmap_difference (del[bb->index], antloc[bb->index], | |
360 laterin[bb->index]); | |
361 | |
362 for (x = 0; x < NUM_EDGES (edge_list); x++) | |
363 { | |
364 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); | |
365 | |
366 if (b == EXIT_BLOCK_PTR) | |
367 sbitmap_difference (insert[x], later[x], laterin[last_basic_block]); | |
368 else | |
369 sbitmap_difference (insert[x], later[x], laterin[b->index]); | |
370 } | |
371 } | |
372 | |
373 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and | |
374 delete vectors for edge based LCM. Returns an edgelist which is used to | |
375 map the insert vector to what edge an expression should be inserted on. */ | |
376 | |
377 struct edge_list * | |
378 pre_edge_lcm (int n_exprs, sbitmap *transp, | |
379 sbitmap *avloc, sbitmap *antloc, sbitmap *kill, | |
380 sbitmap **insert, sbitmap **del) | |
381 { | |
382 sbitmap *antin, *antout, *earliest; | |
383 sbitmap *avin, *avout; | |
384 sbitmap *later, *laterin; | |
385 struct edge_list *edge_list; | |
386 int num_edges; | |
387 | |
388 edge_list = create_edge_list (); | |
389 num_edges = NUM_EDGES (edge_list); | |
390 | |
391 #ifdef LCM_DEBUG_INFO | |
392 if (dump_file) | |
393 { | |
394 fprintf (dump_file, "Edge List:\n"); | |
395 verify_edge_list (dump_file, edge_list); | |
396 print_edge_list (dump_file, edge_list); | |
397 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); | |
398 dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block); | |
399 dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block); | |
400 dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block); | |
401 } | |
402 #endif | |
403 | |
404 /* Compute global availability. */ | |
405 avin = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
406 avout = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
407 compute_available (avloc, kill, avout, avin); | |
408 sbitmap_vector_free (avin); | |
409 | |
410 /* Compute global anticipatability. */ | |
411 antin = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
412 antout = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
413 compute_antinout_edge (antloc, transp, antin, antout); | |
414 | |
415 #ifdef LCM_DEBUG_INFO | |
416 if (dump_file) | |
417 { | |
418 dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block); | |
419 dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block); | |
420 } | |
421 #endif | |
422 | |
423 /* Compute earliestness. */ | |
424 earliest = sbitmap_vector_alloc (num_edges, n_exprs); | |
425 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); | |
426 | |
427 #ifdef LCM_DEBUG_INFO | |
428 if (dump_file) | |
429 dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges); | |
430 #endif | |
431 | |
432 sbitmap_vector_free (antout); | |
433 sbitmap_vector_free (antin); | |
434 sbitmap_vector_free (avout); | |
435 | |
436 later = sbitmap_vector_alloc (num_edges, n_exprs); | |
437 | |
438 /* Allocate an extra element for the exit block in the laterin vector. */ | |
439 laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); | |
440 compute_laterin (edge_list, earliest, antloc, later, laterin); | |
441 | |
442 #ifdef LCM_DEBUG_INFO | |
443 if (dump_file) | |
444 { | |
445 dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1); | |
446 dump_sbitmap_vector (dump_file, "later", "", later, num_edges); | |
447 } | |
448 #endif | |
449 | |
450 sbitmap_vector_free (earliest); | |
451 | |
452 *insert = sbitmap_vector_alloc (num_edges, n_exprs); | |
453 *del = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
454 sbitmap_vector_zero (*insert, num_edges); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
455 sbitmap_vector_zero (*del, last_basic_block); |
0 | 456 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del); |
457 | |
458 sbitmap_vector_free (laterin); | |
459 sbitmap_vector_free (later); | |
460 | |
461 #ifdef LCM_DEBUG_INFO | |
462 if (dump_file) | |
463 { | |
464 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); | |
465 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, | |
466 last_basic_block); | |
467 } | |
468 #endif | |
469 | |
470 return edge_list; | |
471 } | |
472 | |
473 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. | |
474 Return the number of passes we performed to iterate to a solution. */ | |
475 | |
476 void | |
477 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, | |
478 sbitmap *avin) | |
479 { | |
480 edge e; | |
481 basic_block *worklist, *qin, *qout, *qend, bb; | |
482 unsigned int qlen; | |
483 edge_iterator ei; | |
484 | |
485 /* Allocate a worklist array/queue. Entries are only added to the | |
486 list if they were not already on the list. So the size is | |
487 bounded by the number of basic blocks. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
488 qin = qout = worklist = |
0 | 489 XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS); |
490 | |
491 /* We want a maximal solution. */ | |
492 sbitmap_vector_ones (avout, last_basic_block); | |
493 | |
494 /* Put every block on the worklist; this is necessary because of the | |
495 optimistic initialization of AVOUT above. */ | |
496 FOR_EACH_BB (bb) | |
497 { | |
498 *qin++ = bb; | |
499 bb->aux = bb; | |
500 } | |
501 | |
502 qin = worklist; | |
503 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; | |
504 qlen = n_basic_blocks - NUM_FIXED_BLOCKS; | |
505 | |
506 /* Mark blocks which are successors of the entry block so that we | |
507 can easily identify them below. */ | |
508 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) | |
509 e->dest->aux = ENTRY_BLOCK_PTR; | |
510 | |
511 /* Iterate until the worklist is empty. */ | |
512 while (qlen) | |
513 { | |
514 /* Take the first entry off the worklist. */ | |
515 bb = *qout++; | |
516 qlen--; | |
517 | |
518 if (qout >= qend) | |
519 qout = worklist; | |
520 | |
521 /* If one of the predecessor blocks is the ENTRY block, then the | |
522 intersection of avouts is the null set. We can identify such blocks | |
523 by the special value in the AUX field in the block structure. */ | |
524 if (bb->aux == ENTRY_BLOCK_PTR) | |
525 /* Do not clear the aux field for blocks which are successors of the | |
526 ENTRY block. That way we never add then to the worklist again. */ | |
527 sbitmap_zero (avin[bb->index]); | |
528 else | |
529 { | |
530 /* Clear the aux field of this block so that it can be added to | |
531 the worklist again if necessary. */ | |
532 bb->aux = NULL; | |
533 sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index); | |
534 } | |
535 | |
536 if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index], | |
537 avin[bb->index], kill[bb->index])) | |
538 /* If the out state of this block changed, then we need | |
539 to add the successors of this block to the worklist | |
540 if they are not already on the worklist. */ | |
541 FOR_EACH_EDGE (e, ei, bb->succs) | |
542 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) | |
543 { | |
544 *qin++ = e->dest; | |
545 e->dest->aux = e; | |
546 qlen++; | |
547 | |
548 if (qin >= qend) | |
549 qin = worklist; | |
550 } | |
551 } | |
552 | |
553 clear_aux_for_edges (); | |
554 clear_aux_for_blocks (); | |
555 free (worklist); | |
556 } | |
557 | |
558 /* Compute the farthest vector for edge based lcm. */ | |
559 | |
560 static void | |
561 compute_farthest (struct edge_list *edge_list, int n_exprs, | |
562 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin, | |
563 sbitmap *kill, sbitmap *farthest) | |
564 { | |
565 sbitmap difference, temp_bitmap; | |
566 int x, num_edges; | |
567 basic_block pred, succ; | |
568 | |
569 num_edges = NUM_EDGES (edge_list); | |
570 | |
571 difference = sbitmap_alloc (n_exprs); | |
572 temp_bitmap = sbitmap_alloc (n_exprs); | |
573 | |
574 for (x = 0; x < num_edges; x++) | |
575 { | |
576 pred = INDEX_EDGE_PRED_BB (edge_list, x); | |
577 succ = INDEX_EDGE_SUCC_BB (edge_list, x); | |
578 if (succ == EXIT_BLOCK_PTR) | |
579 sbitmap_copy (farthest[x], st_avout[pred->index]); | |
580 else | |
581 { | |
582 if (pred == ENTRY_BLOCK_PTR) | |
583 sbitmap_zero (farthest[x]); | |
584 else | |
585 { | |
586 sbitmap_difference (difference, st_avout[pred->index], | |
587 st_antin[succ->index]); | |
588 sbitmap_not (temp_bitmap, st_avin[succ->index]); | |
589 sbitmap_a_and_b_or_c (farthest[x], difference, | |
590 kill[succ->index], temp_bitmap); | |
591 } | |
592 } | |
593 } | |
594 | |
595 sbitmap_free (temp_bitmap); | |
596 sbitmap_free (difference); | |
597 } | |
598 | |
599 /* Compute nearer and nearerout vectors for edge based lcm. | |
600 | |
601 This is the mirror of compute_laterin, additional comments on the | |
602 implementation can be found before compute_laterin. */ | |
603 | |
604 static void | |
605 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest, | |
606 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout) | |
607 { | |
608 int num_edges, i; | |
609 edge e; | |
610 basic_block *worklist, *tos, bb; | |
611 edge_iterator ei; | |
612 | |
613 num_edges = NUM_EDGES (edge_list); | |
614 | |
615 /* Allocate a worklist array/queue. Entries are only added to the | |
616 list if they were not already on the list. So the size is | |
617 bounded by the number of basic blocks. */ | |
618 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); | |
619 | |
620 /* Initialize NEARER for each edge and build a mapping from an edge to | |
621 its index. */ | |
622 for (i = 0; i < num_edges; i++) | |
623 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; | |
624 | |
625 /* We want a maximal solution. */ | |
626 sbitmap_vector_ones (nearer, num_edges); | |
627 | |
628 /* Note that even though we want an optimistic setting of NEARER, we | |
629 do not want to be overly optimistic. Consider an incoming edge to | |
630 the exit block. That edge should always have a NEARER value the | |
631 same as FARTHEST for that edge. */ | |
632 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) | |
633 sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]); | |
634 | |
635 /* Add all the blocks to the worklist. This prevents an early exit | |
636 from the loop given our optimistic initialization of NEARER. */ | |
637 FOR_EACH_BB (bb) | |
638 { | |
639 *tos++ = bb; | |
640 bb->aux = bb; | |
641 } | |
642 | |
643 /* Iterate until the worklist is empty. */ | |
644 while (tos != worklist) | |
645 { | |
646 /* Take the first entry off the worklist. */ | |
647 bb = *--tos; | |
648 bb->aux = NULL; | |
649 | |
650 /* Compute the intersection of NEARER for each outgoing edge from B. */ | |
651 sbitmap_ones (nearerout[bb->index]); | |
652 FOR_EACH_EDGE (e, ei, bb->succs) | |
653 sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index], | |
654 nearer[(size_t) e->aux]); | |
655 | |
656 /* Calculate NEARER for all incoming edges. */ | |
657 FOR_EACH_EDGE (e, ei, bb->preds) | |
658 if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux], | |
659 farthest[(size_t) e->aux], | |
660 nearerout[e->dest->index], | |
661 st_avloc[e->dest->index]) | |
662 /* If NEARER for an incoming edge was changed, then we need | |
663 to add the source of the incoming edge to the worklist. */ | |
664 && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0) | |
665 { | |
666 *tos++ = e->src; | |
667 e->src->aux = e; | |
668 } | |
669 } | |
670 | |
671 /* Computation of insertion and deletion points requires computing NEAREROUT | |
672 for the ENTRY block. We allocated an extra entry in the NEAREROUT array | |
673 for just this purpose. */ | |
674 sbitmap_ones (nearerout[last_basic_block]); | |
675 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) | |
676 sbitmap_a_and_b (nearerout[last_basic_block], | |
677 nearerout[last_basic_block], | |
678 nearer[(size_t) e->aux]); | |
679 | |
680 clear_aux_for_edges (); | |
681 free (tos); | |
682 } | |
683 | |
684 /* Compute the insertion and deletion points for edge based LCM. */ | |
685 | |
686 static void | |
687 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc, | |
688 sbitmap *nearer, sbitmap *nearerout, | |
689 sbitmap *insert, sbitmap *del) | |
690 { | |
691 int x; | |
692 basic_block bb; | |
693 | |
694 FOR_EACH_BB (bb) | |
695 sbitmap_difference (del[bb->index], st_avloc[bb->index], | |
696 nearerout[bb->index]); | |
697 | |
698 for (x = 0; x < NUM_EDGES (edge_list); x++) | |
699 { | |
700 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x); | |
701 if (b == ENTRY_BLOCK_PTR) | |
702 sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]); | |
703 else | |
704 sbitmap_difference (insert[x], nearer[x], nearerout[b->index]); | |
705 } | |
706 } | |
707 | |
708 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the | |
709 insert and delete vectors for edge based reverse LCM. Returns an | |
710 edgelist which is used to map the insert vector to what edge | |
711 an expression should be inserted on. */ | |
712 | |
713 struct edge_list * | |
714 pre_edge_rev_lcm (int n_exprs, sbitmap *transp, | |
715 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, | |
716 sbitmap **insert, sbitmap **del) | |
717 { | |
718 sbitmap *st_antin, *st_antout; | |
719 sbitmap *st_avout, *st_avin, *farthest; | |
720 sbitmap *nearer, *nearerout; | |
721 struct edge_list *edge_list; | |
722 int num_edges; | |
723 | |
724 edge_list = create_edge_list (); | |
725 num_edges = NUM_EDGES (edge_list); | |
726 | |
727 st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
728 st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
729 sbitmap_vector_zero (st_antin, last_basic_block); | |
730 sbitmap_vector_zero (st_antout, last_basic_block); | |
731 compute_antinout_edge (st_antloc, transp, st_antin, st_antout); | |
732 | |
733 /* Compute global anticipatability. */ | |
734 st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
735 st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
736 compute_available (st_avloc, kill, st_avout, st_avin); | |
737 | |
738 #ifdef LCM_DEBUG_INFO | |
739 if (dump_file) | |
740 { | |
741 fprintf (dump_file, "Edge List:\n"); | |
742 verify_edge_list (dump_file, edge_list); | |
743 print_edge_list (dump_file, edge_list); | |
744 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); | |
745 dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); | |
746 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); | |
747 dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block); | |
748 dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block); | |
749 dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block); | |
750 } | |
751 #endif | |
752 | |
753 #ifdef LCM_DEBUG_INFO | |
754 if (dump_file) | |
755 { | |
756 dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block); | |
757 dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block); | |
758 } | |
759 #endif | |
760 | |
761 /* Compute farthestness. */ | |
762 farthest = sbitmap_vector_alloc (num_edges, n_exprs); | |
763 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin, | |
764 kill, farthest); | |
765 | |
766 #ifdef LCM_DEBUG_INFO | |
767 if (dump_file) | |
768 dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges); | |
769 #endif | |
770 | |
771 sbitmap_vector_free (st_antin); | |
772 sbitmap_vector_free (st_antout); | |
773 | |
774 sbitmap_vector_free (st_avin); | |
775 sbitmap_vector_free (st_avout); | |
776 | |
777 nearer = sbitmap_vector_alloc (num_edges, n_exprs); | |
778 | |
779 /* Allocate an extra element for the entry block. */ | |
780 nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); | |
781 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout); | |
782 | |
783 #ifdef LCM_DEBUG_INFO | |
784 if (dump_file) | |
785 { | |
786 dump_sbitmap_vector (dump_file, "nearerout", "", nearerout, | |
787 last_basic_block + 1); | |
788 dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges); | |
789 } | |
790 #endif | |
791 | |
792 sbitmap_vector_free (farthest); | |
793 | |
794 *insert = sbitmap_vector_alloc (num_edges, n_exprs); | |
795 *del = sbitmap_vector_alloc (last_basic_block, n_exprs); | |
796 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, | |
797 *insert, *del); | |
798 | |
799 sbitmap_vector_free (nearerout); | |
800 sbitmap_vector_free (nearer); | |
801 | |
802 #ifdef LCM_DEBUG_INFO | |
803 if (dump_file) | |
804 { | |
805 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); | |
806 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, | |
807 last_basic_block); | |
808 } | |
809 #endif | |
810 return edge_list; | |
811 } | |
812 |