Branch data Line data Source code
1 : : /* Generic partial redundancy elimination with lazy code motion support.
2 : : Copyright (C) 1998-2024 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 : 473335 : compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
81 : : sbitmap *antout)
82 : : {
83 : 473335 : basic_block bb;
84 : 473335 : edge e;
85 : 473335 : basic_block *worklist, *qin, *qout, *qend;
86 : 473335 : unsigned int qlen;
87 : 473335 : 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 : 473335 : 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 : 473335 : 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 : 473335 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
103 : 473335 : int n = inverted_rev_post_order_compute (cfun, rpo);
104 : 10383691 : for (int i = 0; i < n; ++i)
105 : : {
106 : 9910356 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
107 : 9910356 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
108 : 9437021 : || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
109 : 946670 : continue;
110 : 8963686 : *qin++ = bb;
111 : 8963686 : bb->aux = bb;
112 : : }
113 : 473335 : free (rpo);
114 : :
115 : 473335 : qin = worklist;
116 : 473335 : qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
117 : 473335 : 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 : 1353177 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
122 : 879842 : e->src->aux = EXIT_BLOCK_PTR_FOR_FN (cfun);
123 : :
124 : : /* Iterate until the worklist is empty. */
125 : 10341112 : while (qlen)
126 : : {
127 : : /* Take the first entry off the worklist. */
128 : 9867777 : bb = *qout++;
129 : 9867777 : qlen--;
130 : :
131 : 9867777 : if (qout >= qend)
132 : 473911 : qout = worklist;
133 : :
134 : 9867777 : 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 : 879842 : 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 : 8987935 : bb->aux = NULL;
144 : 8987935 : bitmap_intersection_of_succs (antout[bb->index], antin, bb);
145 : : }
146 : :
147 : 9867777 : if (bitmap_or_and (antin[bb->index], antloc[bb->index],
148 : 9867777 : 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 : 22691632 : FOR_EACH_EDGE (e, ei, bb->preds)
153 : 13525481 : if (!e->src->aux && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
154 : : {
155 : 904091 : *qin++ = e->src;
156 : 904091 : e->src->aux = e;
157 : 904091 : qlen++;
158 : 904091 : if (qin >= qend)
159 : 576 : qin = worklist;
160 : : }
161 : : }
162 : :
163 : 473335 : clear_aux_for_edges ();
164 : 473335 : clear_aux_for_blocks ();
165 : 473335 : free (worklist);
166 : 473335 : }
167 : :
168 : : /* Compute the earliest vector for edge based lcm. */
169 : :
170 : : void
171 : 473303 : compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
172 : : sbitmap *antout, sbitmap *avout, sbitmap *kill,
173 : : sbitmap *earliest)
174 : : {
175 : 473303 : int x, num_edges;
176 : 473303 : basic_block pred, succ;
177 : :
178 : 473303 : num_edges = NUM_EDGES (edge_list);
179 : :
180 : 473303 : auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
181 : 15055978 : for (x = 0; x < num_edges; x++)
182 : : {
183 : 14109372 : pred = INDEX_EDGE_PRED_BB (edge_list, x);
184 : 14109372 : succ = INDEX_EDGE_SUCC_BB (edge_list, x);
185 : 14109372 : if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
186 : 473303 : bitmap_copy (earliest[x], antin[succ->index]);
187 : : else
188 : : {
189 : 13636069 : if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
190 : 879809 : bitmap_clear (earliest[x]);
191 : : else
192 : : {
193 : 12756260 : bitmap_and_compl (difference, antin[succ->index],
194 : 12756260 : avout[pred->index]);
195 : 12756260 : bitmap_not (temp_bitmap, antout[pred->index]);
196 : 12756260 : bitmap_and_or (earliest[x], difference,
197 : 12756260 : kill[pred->index], temp_bitmap);
198 : : }
199 : : }
200 : : }
201 : 473303 : }
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 : 473303 : compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
234 : : sbitmap *antloc, sbitmap *later, sbitmap *laterin)
235 : : {
236 : 473303 : int num_edges, i;
237 : 473303 : edge e;
238 : 473303 : basic_block *worklist, *qin, *qout, *qend, bb;
239 : 473303 : unsigned int qlen;
240 : 473303 : edge_iterator ei;
241 : :
242 : 473303 : 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 : 473303 : qin = qout = worklist
248 : 473303 : = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
249 : :
250 : : /* Initialize a mapping from each edge to its index. */
251 : 15055978 : for (i = 0; i < num_edges; i++)
252 : 14109372 : 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 : 473303 : 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 : 946606 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
271 : 473303 : 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 : 473303 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
276 : 473303 : int n = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, false);
277 : 9436850 : for (int i = 0; i < n; ++i)
278 : : {
279 : 8963547 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
280 : 8963547 : *qin++ = bb;
281 : 8963547 : bb->aux = bb;
282 : : }
283 : 473303 : 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 : 473303 : qin = worklist;
288 : 473303 : qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
289 : 473303 : qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
290 : :
291 : : /* Iterate until the worklist is empty. */
292 : 10135651 : while (qlen)
293 : : {
294 : : /* Take the first entry off the worklist. */
295 : 9662348 : bb = *qout++;
296 : 9662348 : bb->aux = NULL;
297 : 9662348 : qlen--;
298 : 9662348 : if (qout >= qend)
299 : 473788 : qout = worklist;
300 : :
301 : : /* Compute LATERIN as the intersection of LATER for each incoming
302 : : edge to BB. */
303 : 9662348 : bitmap_ones (laterin[bb->index]);
304 : 24436799 : FOR_EACH_EDGE (e, ei, bb->preds)
305 : 14774451 : bitmap_and (laterin[bb->index], laterin[bb->index],
306 : 14774451 : later[(size_t)e->aux]);
307 : :
308 : : /* Calculate LATER for all outgoing edges of BB. */
309 : 24586276 : FOR_EACH_EDGE (e, ei, bb->succs)
310 : 14923928 : if (bitmap_ior_and_compl (later[(size_t) e->aux],
311 : 14923928 : earliest[(size_t) e->aux],
312 : 14923928 : laterin[bb->index],
313 : 14923928 : 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 : 14923928 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest->aux == 0)
317 : : {
318 : 698801 : *qin++ = e->dest;
319 : 698801 : e->dest->aux = e;
320 : 698801 : qlen++;
321 : 698801 : if (qin >= qend)
322 : 485 : 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 : 473303 : bitmap_ones (laterin[last_basic_block_for_fn (cfun)]);
330 : 1353112 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
331 : 879809 : bitmap_and (laterin[last_basic_block_for_fn (cfun)],
332 : 879809 : laterin[last_basic_block_for_fn (cfun)],
333 : 879809 : later[(size_t) e->aux]);
334 : :
335 : 473303 : clear_aux_for_edges ();
336 : 473303 : free (worklist);
337 : 473303 : }
338 : :
339 : : /* Compute the insertion and deletion points for edge based LCM. */
340 : :
341 : : static void
342 : 473303 : compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
343 : : sbitmap *later, sbitmap *laterin, sbitmap *insert,
344 : : sbitmap *del)
345 : : {
346 : 473303 : int x;
347 : 473303 : basic_block bb;
348 : :
349 : 9436850 : FOR_EACH_BB_FN (bb, cfun)
350 : 8963547 : bitmap_and_compl (del[bb->index], antloc[bb->index],
351 : 8963547 : laterin[bb->index]);
352 : :
353 : 14582675 : for (x = 0; x < NUM_EDGES (edge_list); x++)
354 : : {
355 : 14109372 : basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
356 : :
357 : 14109372 : if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
358 : 879809 : bitmap_and_compl (insert[x], later[x],
359 : 879809 : laterin[last_basic_block_for_fn (cfun)]);
360 : : else
361 : 13229563 : bitmap_and_compl (insert[x], later[x], laterin[b->index]);
362 : : }
363 : 473303 : }
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 : 473303 : 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 : 473303 : sbitmap *antin, *antout, *earliest;
376 : 473303 : sbitmap *later, *laterin;
377 : 473303 : struct edge_list *edge_list;
378 : 473303 : int num_edges;
379 : :
380 : 473303 : edge_list = create_edge_list ();
381 : 473303 : 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 : 473303 : compute_available (avloc, kill, avout, avin);
402 : :
403 : : /* Compute global anticipatability. */
404 : 473303 : antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
405 : 473303 : antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
406 : 473303 : 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 : 473303 : earliest = sbitmap_vector_alloc (num_edges, n_exprs);
420 : 473303 : 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 : 473303 : sbitmap_vector_free (antout);
428 : 473303 : sbitmap_vector_free (antin);
429 : :
430 : 473303 : later = sbitmap_vector_alloc (num_edges, n_exprs);
431 : :
432 : : /* Allocate an extra element for the exit block in the laterin vector. */
433 : 473303 : laterin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
434 : : n_exprs);
435 : 473303 : 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 : 473303 : sbitmap_vector_free (earliest);
447 : :
448 : 473303 : *insert = sbitmap_vector_alloc (num_edges, n_exprs);
449 : 473303 : *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
450 : 473303 : bitmap_vector_clear (*insert, num_edges);
451 : 473303 : bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
452 : 473303 : compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
453 : :
454 : 473303 : sbitmap_vector_free (laterin);
455 : 473303 : 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 : 473303 : return edge_list;
467 : : }
468 : :
469 : : /* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */
470 : :
471 : : struct edge_list *
472 : 397397 : pre_edge_lcm (int n_exprs, sbitmap *transp,
473 : : sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
474 : : sbitmap **insert, sbitmap **del)
475 : : {
476 : 397397 : struct edge_list *edge_list;
477 : 397397 : sbitmap *avin, *avout;
478 : :
479 : 397397 : avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
480 : 397397 : avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
481 : :
482 : 397397 : edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
483 : : avin, avout, insert, del);
484 : :
485 : 397397 : sbitmap_vector_free (avout);
486 : 397397 : sbitmap_vector_free (avin);
487 : :
488 : 397397 : 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 : 1778088 : compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
496 : : sbitmap *avin)
497 : : {
498 : 1778088 : edge e;
499 : 1778088 : basic_block *worklist, *qin, *qout, *qend, bb;
500 : 1778088 : unsigned int qlen;
501 : 1778088 : 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 : 3556176 : qin = qout = worklist =
507 : 1778088 : XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
508 : :
509 : : /* We want a maximal solution. */
510 : 1778088 : 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 : 1778088 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
516 : 1778088 : int n = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, false);
517 : 39225763 : for (int i = 0; i < n; ++i)
518 : : {
519 : 37447675 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
520 : 37447675 : *qin++ = bb;
521 : 37447675 : bb->aux = bb;
522 : : }
523 : 1778088 : free (rpo);
524 : :
525 : 1778088 : qin = worklist;
526 : 1778088 : qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
527 : 1778088 : 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 : 3556176 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
532 : 1778088 : e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun);
533 : :
534 : : /* Iterate until the worklist is empty. */
535 : 55629033 : while (qlen)
536 : : {
537 : : /* Take the first entry off the worklist. */
538 : 53850945 : bb = *qout++;
539 : 53850945 : qlen--;
540 : :
541 : 53850945 : if (qout >= qend)
542 : 1888222 : 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 : 53850945 : 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 : 1778088 : 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 : 52072857 : bb->aux = NULL;
556 : 52072857 : bitmap_intersection_of_preds (avin[bb->index], avout, bb);
557 : : }
558 : :
559 : 53850945 : if (bitmap_ior_and_compl (avout[bb->index], avloc[bb->index],
560 : 53850945 : 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 : 118357247 : FOR_EACH_EDGE (e, ei, bb->succs)
565 : 70830776 : if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
566 : : {
567 : 16403270 : *qin++ = e->dest;
568 : 16403270 : e->dest->aux = e;
569 : 16403270 : qlen++;
570 : :
571 : 16403270 : if (qin >= qend)
572 : 110134 : qin = worklist;
573 : : }
574 : : }
575 : :
576 : 1778088 : clear_aux_for_edges ();
577 : 1778088 : clear_aux_for_blocks ();
578 : 1778088 : free (worklist);
579 : 1778088 : }
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 : 293 : for (x = 0; x < num_edges; x++)
595 : : {
596 : 229 : pred = INDEX_EDGE_PRED_BB (edge_list, x);
597 : 229 : succ = INDEX_EDGE_SUCC_BB (edge_list, x);
598 : 229 : if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
599 : 33 : bitmap_copy (farthest[x], st_avout[pred->index]);
600 : : else
601 : : {
602 : 196 : if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
603 : 32 : bitmap_clear (farthest[x]);
604 : : else
605 : : {
606 : 164 : bitmap_and_compl (difference, st_avout[pred->index],
607 : 164 : st_antin[succ->index]);
608 : 164 : bitmap_not (temp_bitmap, st_avin[succ->index]);
609 : 164 : bitmap_and_or (farthest[x], difference,
610 : 164 : 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 : 293 : for (i = 0; i < num_edges; i++)
640 : 229 : 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 : 171 : FOR_EACH_BB_FN (bb, cfun)
655 : : {
656 : 139 : *tos++ = bb;
657 : 139 : bb->aux = bb;
658 : : }
659 : :
660 : : /* Iterate until the worklist is empty. */
661 : 192 : while (tos != worklist)
662 : : {
663 : : /* Take the first entry off the worklist. */
664 : 160 : bb = *--tos;
665 : 160 : bb->aux = NULL;
666 : :
667 : : /* Compute the intersection of NEARER for each outgoing edge from B. */
668 : 160 : bitmap_ones (nearerout[bb->index]);
669 : 394 : FOR_EACH_EDGE (e, ei, bb->succs)
670 : 234 : bitmap_and (nearerout[bb->index], nearerout[bb->index],
671 : 234 : nearer[(size_t) e->aux]);
672 : :
673 : : /* Calculate NEARER for all incoming edges. */
674 : 390 : FOR_EACH_EDGE (e, ei, bb->preds)
675 : 230 : if (bitmap_ior_and_compl (nearer[(size_t) e->aux],
676 : 230 : farthest[(size_t) e->aux],
677 : 230 : nearerout[e->dest->index],
678 : 230 : 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 : 230 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && e->src->aux == 0)
682 : : {
683 : 21 : *tos++ = e->src;
684 : 21 : 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 : 171 : FOR_EACH_BB_FN (bb, cfun)
712 : 139 : bitmap_and_compl (del[bb->index], st_avloc[bb->index],
713 : 139 : nearerout[bb->index]);
714 : :
715 : 261 : for (x = 0; x < NUM_EDGES (edge_list); x++)
716 : : {
717 : 229 : basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
718 : 229 : 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 : 197 : 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 : :
|
