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