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