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