Mercurial > hg > CbC > CbC_gcc
annotate gcc/cfganal.c @ 66:b362627d71ba
bug-fix: modify tail-call-optimization enforcing rules. (calls.c.)
| author | Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 14 Dec 2010 03:58:33 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Control flow graph analysis code for GNU compiler. |
| 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
| 3 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008 | |
| 4 Free Software Foundation, Inc. | |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify it under | |
| 9 the terms of the GNU General Public License as published by the Free | |
| 10 Software Foundation; either version 3, or (at your option) any later | |
| 11 version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 /* This file contains various simple utilities to analyze the CFG. */ | |
| 23 #include "config.h" | |
| 24 #include "system.h" | |
| 25 #include "coretypes.h" | |
| 26 #include "tm.h" | |
| 27 #include "rtl.h" | |
| 28 #include "obstack.h" | |
| 29 #include "hard-reg-set.h" | |
| 30 #include "basic-block.h" | |
| 31 #include "insn-config.h" | |
| 32 #include "recog.h" | |
| 33 #include "toplev.h" | |
| 34 #include "tm_p.h" | |
| 35 #include "vec.h" | |
| 36 #include "vecprim.h" | |
| 37 #include "timevar.h" | |
| 38 | |
| 39 /* Store the data structures necessary for depth-first search. */ | |
| 40 struct depth_first_search_dsS { | |
| 41 /* stack for backtracking during the algorithm */ | |
| 42 basic_block *stack; | |
| 43 | |
| 44 /* number of edges in the stack. That is, positions 0, ..., sp-1 | |
| 45 have edges. */ | |
| 46 unsigned int sp; | |
| 47 | |
| 48 /* record of basic blocks already seen by depth-first search */ | |
| 49 sbitmap visited_blocks; | |
| 50 }; | |
| 51 typedef struct depth_first_search_dsS *depth_first_search_ds; | |
| 52 | |
| 53 static void flow_dfs_compute_reverse_init (depth_first_search_ds); | |
| 54 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds, | |
| 55 basic_block); | |
| 56 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds, | |
| 57 basic_block); | |
| 58 static void flow_dfs_compute_reverse_finish (depth_first_search_ds); | |
| 59 static bool flow_active_insn_p (const_rtx); | |
| 60 | |
| 61 /* Like active_insn_p, except keep the return value clobber around | |
| 62 even after reload. */ | |
| 63 | |
| 64 static bool | |
| 65 flow_active_insn_p (const_rtx insn) | |
| 66 { | |
| 67 if (active_insn_p (insn)) | |
| 68 return true; | |
| 69 | |
| 70 /* A clobber of the function return value exists for buggy | |
| 71 programs that fail to return a value. Its effect is to | |
| 72 keep the return value from being live across the entire | |
| 73 function. If we allow it to be skipped, we introduce the | |
| 74 possibility for register lifetime confusion. */ | |
| 75 if (GET_CODE (PATTERN (insn)) == CLOBBER | |
| 76 && REG_P (XEXP (PATTERN (insn), 0)) | |
| 77 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) | |
| 78 return true; | |
| 79 | |
| 80 return false; | |
| 81 } | |
| 82 | |
| 83 /* Return true if the block has no effect and only forwards control flow to | |
| 84 its single destination. */ | |
| 85 | |
| 86 bool | |
| 87 forwarder_block_p (const_basic_block bb) | |
| 88 { | |
| 89 rtx insn; | |
| 90 | |
| 91 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR | |
| 92 || !single_succ_p (bb)) | |
| 93 return false; | |
| 94 | |
| 95 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) | |
| 96 if (INSN_P (insn) && flow_active_insn_p (insn)) | |
| 97 return false; | |
| 98 | |
| 99 return (!INSN_P (insn) | |
| 100 || (JUMP_P (insn) && simplejump_p (insn)) | |
| 101 || !flow_active_insn_p (insn)); | |
| 102 } | |
| 103 | |
| 104 /* Return nonzero if we can reach target from src by falling through. */ | |
| 105 | |
| 106 bool | |
| 107 can_fallthru (basic_block src, basic_block target) | |
| 108 { | |
| 109 rtx insn = BB_END (src); | |
| 110 rtx insn2; | |
| 111 edge e; | |
| 112 edge_iterator ei; | |
| 113 | |
| 114 if (target == EXIT_BLOCK_PTR) | |
| 115 return true; | |
| 116 if (src->next_bb != target) | |
| 117 return 0; | |
| 118 FOR_EACH_EDGE (e, ei, src->succs) | |
| 119 if (e->dest == EXIT_BLOCK_PTR | |
| 120 && e->flags & EDGE_FALLTHRU) | |
| 121 return 0; | |
| 122 | |
| 123 insn2 = BB_HEAD (target); | |
| 124 if (insn2 && !active_insn_p (insn2)) | |
| 125 insn2 = next_active_insn (insn2); | |
| 126 | |
| 127 /* ??? Later we may add code to move jump tables offline. */ | |
| 128 return next_active_insn (insn) == insn2; | |
| 129 } | |
| 130 | |
| 131 /* Return nonzero if we could reach target from src by falling through, | |
| 132 if the target was made adjacent. If we already have a fall-through | |
| 133 edge to the exit block, we can't do that. */ | |
| 134 bool | |
| 135 could_fall_through (basic_block src, basic_block target) | |
| 136 { | |
| 137 edge e; | |
| 138 edge_iterator ei; | |
| 139 | |
| 140 if (target == EXIT_BLOCK_PTR) | |
| 141 return true; | |
| 142 FOR_EACH_EDGE (e, ei, src->succs) | |
| 143 if (e->dest == EXIT_BLOCK_PTR | |
| 144 && e->flags & EDGE_FALLTHRU) | |
| 145 return 0; | |
| 146 return true; | |
| 147 } | |
| 148 | |
| 149 /* Mark the back edges in DFS traversal. | |
| 150 Return nonzero if a loop (natural or otherwise) is present. | |
| 151 Inspired by Depth_First_Search_PP described in: | |
| 152 | |
| 153 Advanced Compiler Design and Implementation | |
| 154 Steven Muchnick | |
| 155 Morgan Kaufmann, 1997 | |
| 156 | |
| 157 and heavily borrowed from pre_and_rev_post_order_compute. */ | |
| 158 | |
| 159 bool | |
| 160 mark_dfs_back_edges (void) | |
| 161 { | |
| 162 edge_iterator *stack; | |
| 163 int *pre; | |
| 164 int *post; | |
| 165 int sp; | |
| 166 int prenum = 1; | |
| 167 int postnum = 1; | |
| 168 sbitmap visited; | |
| 169 bool found = false; | |
| 170 | |
| 171 /* Allocate the preorder and postorder number arrays. */ | |
| 172 pre = XCNEWVEC (int, last_basic_block); | |
| 173 post = XCNEWVEC (int, last_basic_block); | |
| 174 | |
| 175 /* Allocate stack for back-tracking up CFG. */ | |
| 176 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
| 177 sp = 0; | |
| 178 | |
| 179 /* Allocate bitmap to track nodes that have been visited. */ | |
| 180 visited = sbitmap_alloc (last_basic_block); | |
| 181 | |
| 182 /* None of the nodes in the CFG have been visited yet. */ | |
| 183 sbitmap_zero (visited); | |
| 184 | |
| 185 /* Push the first edge on to the stack. */ | |
| 186 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); | |
| 187 | |
| 188 while (sp) | |
| 189 { | |
| 190 edge_iterator ei; | |
| 191 basic_block src; | |
| 192 basic_block dest; | |
| 193 | |
| 194 /* Look at the edge on the top of the stack. */ | |
| 195 ei = stack[sp - 1]; | |
| 196 src = ei_edge (ei)->src; | |
| 197 dest = ei_edge (ei)->dest; | |
| 198 ei_edge (ei)->flags &= ~EDGE_DFS_BACK; | |
| 199 | |
| 200 /* Check if the edge destination has been visited yet. */ | |
| 201 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) | |
| 202 { | |
| 203 /* Mark that we have visited the destination. */ | |
| 204 SET_BIT (visited, dest->index); | |
| 205 | |
| 206 pre[dest->index] = prenum++; | |
| 207 if (EDGE_COUNT (dest->succs) > 0) | |
| 208 { | |
| 209 /* Since the DEST node has been visited for the first | |
| 210 time, check its successors. */ | |
| 211 stack[sp++] = ei_start (dest->succs); | |
| 212 } | |
| 213 else | |
| 214 post[dest->index] = postnum++; | |
| 215 } | |
| 216 else | |
| 217 { | |
| 218 if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR | |
| 219 && pre[src->index] >= pre[dest->index] | |
| 220 && post[dest->index] == 0) | |
| 221 ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; | |
| 222 | |
| 223 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) | |
| 224 post[src->index] = postnum++; | |
| 225 | |
| 226 if (!ei_one_before_end_p (ei)) | |
| 227 ei_next (&stack[sp - 1]); | |
| 228 else | |
| 229 sp--; | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 free (pre); | |
| 234 free (post); | |
| 235 free (stack); | |
| 236 sbitmap_free (visited); | |
| 237 | |
| 238 return found; | |
| 239 } | |
| 240 | |
| 241 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ | |
| 242 | |
| 243 void | |
| 244 set_edge_can_fallthru_flag (void) | |
| 245 { | |
| 246 basic_block bb; | |
| 247 | |
| 248 FOR_EACH_BB (bb) | |
| 249 { | |
| 250 edge e; | |
| 251 edge_iterator ei; | |
| 252 | |
| 253 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 254 { | |
| 255 e->flags &= ~EDGE_CAN_FALLTHRU; | |
| 256 | |
| 257 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ | |
| 258 if (e->flags & EDGE_FALLTHRU) | |
| 259 e->flags |= EDGE_CAN_FALLTHRU; | |
| 260 } | |
| 261 | |
| 262 /* If the BB ends with an invertible condjump all (2) edges are | |
| 263 CAN_FALLTHRU edges. */ | |
| 264 if (EDGE_COUNT (bb->succs) != 2) | |
| 265 continue; | |
| 266 if (!any_condjump_p (BB_END (bb))) | |
| 267 continue; | |
| 268 if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0)) | |
| 269 continue; | |
| 270 invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0); | |
| 271 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU; | |
| 272 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU; | |
| 273 } | |
| 274 } | |
| 275 | |
| 276 /* Find unreachable blocks. An unreachable block will have 0 in | |
| 277 the reachable bit in block->flags. A nonzero value indicates the | |
| 278 block is reachable. */ | |
| 279 | |
| 280 void | |
| 281 find_unreachable_blocks (void) | |
| 282 { | |
| 283 edge e; | |
| 284 edge_iterator ei; | |
| 285 basic_block *tos, *worklist, bb; | |
| 286 | |
| 287 tos = worklist = XNEWVEC (basic_block, n_basic_blocks); | |
| 288 | |
| 289 /* Clear all the reachability flags. */ | |
| 290 | |
| 291 FOR_EACH_BB (bb) | |
| 292 bb->flags &= ~BB_REACHABLE; | |
| 293 | |
| 294 /* Add our starting points to the worklist. Almost always there will | |
| 295 be only one. It isn't inconceivable that we might one day directly | |
| 296 support Fortran alternate entry points. */ | |
| 297 | |
| 298 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) | |
| 299 { | |
| 300 *tos++ = e->dest; | |
| 301 | |
| 302 /* Mark the block reachable. */ | |
| 303 e->dest->flags |= BB_REACHABLE; | |
| 304 } | |
| 305 | |
| 306 /* Iterate: find everything reachable from what we've already seen. */ | |
| 307 | |
| 308 while (tos != worklist) | |
| 309 { | |
| 310 basic_block b = *--tos; | |
| 311 | |
| 312 FOR_EACH_EDGE (e, ei, b->succs) | |
| 313 { | |
| 314 basic_block dest = e->dest; | |
| 315 | |
| 316 if (!(dest->flags & BB_REACHABLE)) | |
| 317 { | |
| 318 *tos++ = dest; | |
| 319 dest->flags |= BB_REACHABLE; | |
| 320 } | |
| 321 } | |
| 322 } | |
| 323 | |
| 324 free (worklist); | |
| 325 } | |
| 326 | |
| 327 /* Functions to access an edge list with a vector representation. | |
| 328 Enough data is kept such that given an index number, the | |
| 329 pred and succ that edge represents can be determined, or | |
| 330 given a pred and a succ, its index number can be returned. | |
| 331 This allows algorithms which consume a lot of memory to | |
| 332 represent the normally full matrix of edge (pred,succ) with a | |
| 333 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no | |
| 334 wasted space in the client code due to sparse flow graphs. */ | |
| 335 | |
| 336 /* This functions initializes the edge list. Basically the entire | |
| 337 flowgraph is processed, and all edges are assigned a number, | |
| 338 and the data structure is filled in. */ | |
| 339 | |
| 340 struct edge_list * | |
| 341 create_edge_list (void) | |
| 342 { | |
| 343 struct edge_list *elist; | |
| 344 edge e; | |
| 345 int num_edges; | |
| 346 int block_count; | |
| 347 basic_block bb; | |
| 348 edge_iterator ei; | |
| 349 | |
| 350 block_count = n_basic_blocks; /* Include the entry and exit blocks. */ | |
| 351 | |
| 352 num_edges = 0; | |
| 353 | |
| 354 /* Determine the number of edges in the flow graph by counting successor | |
| 355 edges on each basic block. */ | |
| 356 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 357 { | |
| 358 num_edges += EDGE_COUNT (bb->succs); | |
| 359 } | |
| 360 | |
| 361 elist = XNEW (struct edge_list); | |
| 362 elist->num_blocks = block_count; | |
| 363 elist->num_edges = num_edges; | |
| 364 elist->index_to_edge = XNEWVEC (edge, num_edges); | |
| 365 | |
| 366 num_edges = 0; | |
| 367 | |
| 368 /* Follow successors of blocks, and register these edges. */ | |
| 369 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 370 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 371 elist->index_to_edge[num_edges++] = e; | |
| 372 | |
| 373 return elist; | |
| 374 } | |
| 375 | |
| 376 /* This function free's memory associated with an edge list. */ | |
| 377 | |
| 378 void | |
| 379 free_edge_list (struct edge_list *elist) | |
| 380 { | |
| 381 if (elist) | |
| 382 { | |
| 383 free (elist->index_to_edge); | |
| 384 free (elist); | |
| 385 } | |
| 386 } | |
| 387 | |
| 388 /* This function provides debug output showing an edge list. */ | |
| 389 | |
| 390 void | |
| 391 print_edge_list (FILE *f, struct edge_list *elist) | |
| 392 { | |
| 393 int x; | |
| 394 | |
| 395 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", | |
| 396 elist->num_blocks, elist->num_edges); | |
| 397 | |
| 398 for (x = 0; x < elist->num_edges; x++) | |
| 399 { | |
| 400 fprintf (f, " %-4d - edge(", x); | |
| 401 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) | |
| 402 fprintf (f, "entry,"); | |
| 403 else | |
| 404 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); | |
| 405 | |
| 406 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) | |
| 407 fprintf (f, "exit)\n"); | |
| 408 else | |
| 409 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); | |
| 410 } | |
| 411 } | |
| 412 | |
| 413 /* This function provides an internal consistency check of an edge list, | |
| 414 verifying that all edges are present, and that there are no | |
| 415 extra edges. */ | |
| 416 | |
| 417 void | |
| 418 verify_edge_list (FILE *f, struct edge_list *elist) | |
| 419 { | |
| 420 int pred, succ, index; | |
| 421 edge e; | |
| 422 basic_block bb, p, s; | |
| 423 edge_iterator ei; | |
| 424 | |
| 425 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 426 { | |
| 427 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 428 { | |
| 429 pred = e->src->index; | |
| 430 succ = e->dest->index; | |
| 431 index = EDGE_INDEX (elist, e->src, e->dest); | |
| 432 if (index == EDGE_INDEX_NO_EDGE) | |
| 433 { | |
| 434 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); | |
| 435 continue; | |
| 436 } | |
| 437 | |
| 438 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) | |
| 439 fprintf (f, "*p* Pred for index %d should be %d not %d\n", | |
| 440 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); | |
| 441 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) | |
| 442 fprintf (f, "*p* Succ for index %d should be %d not %d\n", | |
| 443 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); | |
| 444 } | |
| 445 } | |
| 446 | |
| 447 /* We've verified that all the edges are in the list, now lets make sure | |
| 448 there are no spurious edges in the list. */ | |
| 449 | |
| 450 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 451 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) | |
| 452 { | |
| 453 int found_edge = 0; | |
| 454 | |
| 455 FOR_EACH_EDGE (e, ei, p->succs) | |
| 456 if (e->dest == s) | |
| 457 { | |
| 458 found_edge = 1; | |
| 459 break; | |
| 460 } | |
| 461 | |
| 462 FOR_EACH_EDGE (e, ei, s->preds) | |
| 463 if (e->src == p) | |
| 464 { | |
| 465 found_edge = 1; | |
| 466 break; | |
| 467 } | |
| 468 | |
| 469 if (EDGE_INDEX (elist, p, s) | |
| 470 == EDGE_INDEX_NO_EDGE && found_edge != 0) | |
| 471 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", | |
| 472 p->index, s->index); | |
| 473 if (EDGE_INDEX (elist, p, s) | |
| 474 != EDGE_INDEX_NO_EDGE && found_edge == 0) | |
| 475 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", | |
| 476 p->index, s->index, EDGE_INDEX (elist, p, s)); | |
| 477 } | |
| 478 } | |
| 479 | |
| 480 /* Given PRED and SUCC blocks, return the edge which connects the blocks. | |
| 481 If no such edge exists, return NULL. */ | |
| 482 | |
| 483 edge | |
| 484 find_edge (basic_block pred, basic_block succ) | |
| 485 { | |
| 486 edge e; | |
| 487 edge_iterator ei; | |
| 488 | |
| 489 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) | |
| 490 { | |
| 491 FOR_EACH_EDGE (e, ei, pred->succs) | |
| 492 if (e->dest == succ) | |
| 493 return e; | |
| 494 } | |
| 495 else | |
| 496 { | |
| 497 FOR_EACH_EDGE (e, ei, succ->preds) | |
| 498 if (e->src == pred) | |
| 499 return e; | |
| 500 } | |
| 501 | |
| 502 return NULL; | |
| 503 } | |
| 504 | |
| 505 /* This routine will determine what, if any, edge there is between | |
| 506 a specified predecessor and successor. */ | |
| 507 | |
| 508 int | |
| 509 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ) | |
| 510 { | |
| 511 int x; | |
| 512 | |
| 513 for (x = 0; x < NUM_EDGES (edge_list); x++) | |
| 514 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred | |
| 515 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) | |
| 516 return x; | |
| 517 | |
| 518 return (EDGE_INDEX_NO_EDGE); | |
| 519 } | |
| 520 | |
| 521 /* Dump the list of basic blocks in the bitmap NODES. */ | |
| 522 | |
| 523 void | |
| 524 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file) | |
| 525 { | |
| 526 unsigned int node = 0; | |
| 527 sbitmap_iterator sbi; | |
| 528 | |
| 529 if (! nodes) | |
| 530 return; | |
| 531 | |
| 532 fprintf (file, "%s { ", str); | |
| 533 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi) | |
| 534 fprintf (file, "%d ", node); | |
| 535 fputs ("}\n", file); | |
| 536 } | |
| 537 | |
| 538 /* Dump the list of edges in the array EDGE_LIST. */ | |
| 539 | |
| 540 void | |
| 541 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file) | |
| 542 { | |
| 543 int i; | |
| 544 | |
| 545 if (! edge_list) | |
| 546 return; | |
| 547 | |
| 548 fprintf (file, "%s { ", str); | |
| 549 for (i = 0; i < num_edges; i++) | |
| 550 fprintf (file, "%d->%d ", edge_list[i]->src->index, | |
| 551 edge_list[i]->dest->index); | |
| 552 | |
| 553 fputs ("}\n", file); | |
| 554 } | |
| 555 | |
| 556 | |
| 557 /* This routine will remove any fake predecessor edges for a basic block. | |
| 558 When the edge is removed, it is also removed from whatever successor | |
| 559 list it is in. */ | |
| 560 | |
| 561 static void | |
| 562 remove_fake_predecessors (basic_block bb) | |
| 563 { | |
| 564 edge e; | |
| 565 edge_iterator ei; | |
| 566 | |
| 567 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) | |
| 568 { | |
| 569 if ((e->flags & EDGE_FAKE) == EDGE_FAKE) | |
| 570 remove_edge (e); | |
| 571 else | |
| 572 ei_next (&ei); | |
| 573 } | |
| 574 } | |
| 575 | |
| 576 /* This routine will remove all fake edges from the flow graph. If | |
| 577 we remove all fake successors, it will automatically remove all | |
| 578 fake predecessors. */ | |
| 579 | |
| 580 void | |
| 581 remove_fake_edges (void) | |
| 582 { | |
| 583 basic_block bb; | |
| 584 | |
| 585 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) | |
| 586 remove_fake_predecessors (bb); | |
| 587 } | |
| 588 | |
| 589 /* This routine will remove all fake edges to the EXIT_BLOCK. */ | |
| 590 | |
| 591 void | |
| 592 remove_fake_exit_edges (void) | |
| 593 { | |
| 594 remove_fake_predecessors (EXIT_BLOCK_PTR); | |
| 595 } | |
| 596 | |
| 597 | |
| 598 /* This function will add a fake edge between any block which has no | |
| 599 successors, and the exit block. Some data flow equations require these | |
| 600 edges to exist. */ | |
| 601 | |
| 602 void | |
| 603 add_noreturn_fake_exit_edges (void) | |
| 604 { | |
| 605 basic_block bb; | |
| 606 | |
| 607 FOR_EACH_BB (bb) | |
| 608 if (EDGE_COUNT (bb->succs) == 0) | |
| 609 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); | |
| 610 } | |
| 611 | |
| 612 /* This function adds a fake edge between any infinite loops to the | |
| 613 exit block. Some optimizations require a path from each node to | |
| 614 the exit node. | |
| 615 | |
| 616 See also Morgan, Figure 3.10, pp. 82-83. | |
| 617 | |
| 618 The current implementation is ugly, not attempting to minimize the | |
| 619 number of inserted fake edges. To reduce the number of fake edges | |
| 620 to insert, add fake edges from _innermost_ loops containing only | |
| 621 nodes not reachable from the exit block. */ | |
| 622 | |
| 623 void | |
| 624 connect_infinite_loops_to_exit (void) | |
| 625 { | |
| 626 basic_block unvisited_block = EXIT_BLOCK_PTR; | |
| 627 struct depth_first_search_dsS dfs_ds; | |
| 628 | |
| 629 /* Perform depth-first search in the reverse graph to find nodes | |
| 630 reachable from the exit block. */ | |
| 631 flow_dfs_compute_reverse_init (&dfs_ds); | |
| 632 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); | |
| 633 | |
| 634 /* Repeatedly add fake edges, updating the unreachable nodes. */ | |
| 635 while (1) | |
| 636 { | |
| 637 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds, | |
| 638 unvisited_block); | |
| 639 if (!unvisited_block) | |
| 640 break; | |
| 641 | |
| 642 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); | |
| 643 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); | |
| 644 } | |
| 645 | |
| 646 flow_dfs_compute_reverse_finish (&dfs_ds); | |
| 647 return; | |
| 648 } | |
| 649 | |
| 650 /* Compute reverse top sort order. This is computing a post order | |
| 651 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then then | |
| 652 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is | |
| 653 true, unreachable blocks are deleted. */ | |
| 654 | |
| 655 int | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
656 post_order_compute (int *post_order, bool include_entry_exit, |
| 0 | 657 bool delete_unreachable) |
| 658 { | |
| 659 edge_iterator *stack; | |
| 660 int sp; | |
| 661 int post_order_num = 0; | |
| 662 sbitmap visited; | |
| 663 int count; | |
| 664 | |
| 665 if (include_entry_exit) | |
| 666 post_order[post_order_num++] = EXIT_BLOCK; | |
| 667 | |
| 668 /* Allocate stack for back-tracking up CFG. */ | |
| 669 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
| 670 sp = 0; | |
| 671 | |
| 672 /* Allocate bitmap to track nodes that have been visited. */ | |
| 673 visited = sbitmap_alloc (last_basic_block); | |
| 674 | |
| 675 /* None of the nodes in the CFG have been visited yet. */ | |
| 676 sbitmap_zero (visited); | |
| 677 | |
| 678 /* Push the first edge on to the stack. */ | |
| 679 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); | |
| 680 | |
| 681 while (sp) | |
| 682 { | |
| 683 edge_iterator ei; | |
| 684 basic_block src; | |
| 685 basic_block dest; | |
| 686 | |
| 687 /* Look at the edge on the top of the stack. */ | |
| 688 ei = stack[sp - 1]; | |
| 689 src = ei_edge (ei)->src; | |
| 690 dest = ei_edge (ei)->dest; | |
| 691 | |
| 692 /* Check if the edge destination has been visited yet. */ | |
| 693 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) | |
| 694 { | |
| 695 /* Mark that we have visited the destination. */ | |
| 696 SET_BIT (visited, dest->index); | |
| 697 | |
| 698 if (EDGE_COUNT (dest->succs) > 0) | |
| 699 /* Since the DEST node has been visited for the first | |
| 700 time, check its successors. */ | |
| 701 stack[sp++] = ei_start (dest->succs); | |
| 702 else | |
| 703 post_order[post_order_num++] = dest->index; | |
| 704 } | |
| 705 else | |
| 706 { | |
| 707 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) | |
| 708 post_order[post_order_num++] = src->index; | |
| 709 | |
| 710 if (!ei_one_before_end_p (ei)) | |
| 711 ei_next (&stack[sp - 1]); | |
| 712 else | |
| 713 sp--; | |
| 714 } | |
| 715 } | |
| 716 | |
| 717 if (include_entry_exit) | |
| 718 { | |
| 719 post_order[post_order_num++] = ENTRY_BLOCK; | |
| 720 count = post_order_num; | |
| 721 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
722 else |
| 0 | 723 count = post_order_num + 2; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
724 |
| 0 | 725 /* Delete the unreachable blocks if some were found and we are |
| 726 supposed to do it. */ | |
| 727 if (delete_unreachable && (count != n_basic_blocks)) | |
| 728 { | |
| 729 basic_block b; | |
| 730 basic_block next_bb; | |
| 731 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb) | |
| 732 { | |
| 733 next_bb = b->next_bb; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
734 |
| 0 | 735 if (!(TEST_BIT (visited, b->index))) |
| 736 delete_basic_block (b); | |
| 737 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
738 |
| 0 | 739 tidy_fallthru_edges (); |
| 740 } | |
| 741 | |
| 742 free (stack); | |
| 743 sbitmap_free (visited); | |
| 744 return post_order_num; | |
| 745 } | |
| 746 | |
| 747 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
748 /* Helper routine for inverted_post_order_compute. |
| 0 | 749 BB has to belong to a region of CFG |
| 750 unreachable by inverted traversal from the exit. | |
| 751 i.e. there's no control flow path from ENTRY to EXIT | |
| 752 that contains this BB. | |
| 753 This can happen in two cases - if there's an infinite loop | |
| 754 or if there's a block that has no successor | |
| 755 (call to a function with no return). | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
756 Some RTL passes deal with this condition by |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
757 calling connect_infinite_loops_to_exit () and/or |
| 0 | 758 add_noreturn_fake_exit_edges (). |
| 759 However, those methods involve modifying the CFG itself | |
| 760 which may not be desirable. | |
| 761 Hence, we deal with the infinite loop/no return cases | |
| 762 by identifying a unique basic block that can reach all blocks | |
| 763 in such a region by inverted traversal. | |
| 764 This function returns a basic block that guarantees | |
| 765 that all blocks in the region are reachable | |
| 766 by starting an inverted traversal from the returned block. */ | |
| 767 | |
| 768 static basic_block | |
| 769 dfs_find_deadend (basic_block bb) | |
| 770 { | |
| 771 sbitmap visited = sbitmap_alloc (last_basic_block); | |
| 772 sbitmap_zero (visited); | |
| 773 | |
| 774 for (;;) | |
| 775 { | |
| 776 SET_BIT (visited, bb->index); | |
| 777 if (EDGE_COUNT (bb->succs) == 0 | |
| 778 || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index)) | |
| 779 { | |
| 780 sbitmap_free (visited); | |
| 781 return bb; | |
| 782 } | |
| 783 | |
| 784 bb = EDGE_SUCC (bb, 0)->dest; | |
| 785 } | |
| 786 | |
| 787 gcc_unreachable (); | |
| 788 } | |
| 789 | |
| 790 | |
| 791 /* Compute the reverse top sort order of the inverted CFG | |
| 792 i.e. starting from the exit block and following the edges backward | |
| 793 (from successors to predecessors). | |
| 794 This ordering can be used for forward dataflow problems among others. | |
| 795 | |
| 796 This function assumes that all blocks in the CFG are reachable | |
| 797 from the ENTRY (but not necessarily from EXIT). | |
| 798 | |
| 799 If there's an infinite loop, | |
| 800 a simple inverted traversal starting from the blocks | |
| 801 with no successors can't visit all blocks. | |
| 802 To solve this problem, we first do inverted traversal | |
| 803 starting from the blocks with no successor. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
804 And if there's any block left that's not visited by the regular |
| 0 | 805 inverted traversal from EXIT, |
| 806 those blocks are in such problematic region. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
807 Among those, we find one block that has |
| 0 | 808 any visited predecessor (which is an entry into such a region), |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
809 and start looking for a "dead end" from that block |
| 0 | 810 and do another inverted traversal from that block. */ |
| 811 | |
| 812 int | |
| 813 inverted_post_order_compute (int *post_order) | |
| 814 { | |
| 815 basic_block bb; | |
| 816 edge_iterator *stack; | |
| 817 int sp; | |
| 818 int post_order_num = 0; | |
| 819 sbitmap visited; | |
| 820 | |
| 821 /* Allocate stack for back-tracking up CFG. */ | |
| 822 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
| 823 sp = 0; | |
| 824 | |
| 825 /* Allocate bitmap to track nodes that have been visited. */ | |
| 826 visited = sbitmap_alloc (last_basic_block); | |
| 827 | |
| 828 /* None of the nodes in the CFG have been visited yet. */ | |
| 829 sbitmap_zero (visited); | |
| 830 | |
| 831 /* Put all blocks that have no successor into the initial work list. */ | |
| 832 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 833 if (EDGE_COUNT (bb->succs) == 0) | |
| 834 { | |
| 835 /* Push the initial edge on to the stack. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
836 if (EDGE_COUNT (bb->preds) > 0) |
| 0 | 837 { |
| 838 stack[sp++] = ei_start (bb->preds); | |
| 839 SET_BIT (visited, bb->index); | |
| 840 } | |
| 841 } | |
| 842 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
843 do |
| 0 | 844 { |
| 845 bool has_unvisited_bb = false; | |
| 846 | |
| 847 /* The inverted traversal loop. */ | |
| 848 while (sp) | |
| 849 { | |
| 850 edge_iterator ei; | |
| 851 basic_block pred; | |
| 852 | |
| 853 /* Look at the edge on the top of the stack. */ | |
| 854 ei = stack[sp - 1]; | |
| 855 bb = ei_edge (ei)->dest; | |
| 856 pred = ei_edge (ei)->src; | |
| 857 | |
| 858 /* Check if the predecessor has been visited yet. */ | |
| 859 if (! TEST_BIT (visited, pred->index)) | |
| 860 { | |
| 861 /* Mark that we have visited the destination. */ | |
| 862 SET_BIT (visited, pred->index); | |
| 863 | |
| 864 if (EDGE_COUNT (pred->preds) > 0) | |
| 865 /* Since the predecessor node has been visited for the first | |
| 866 time, check its predecessors. */ | |
| 867 stack[sp++] = ei_start (pred->preds); | |
| 868 else | |
| 869 post_order[post_order_num++] = pred->index; | |
| 870 } | |
| 871 else | |
| 872 { | |
| 873 if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei)) | |
| 874 post_order[post_order_num++] = bb->index; | |
| 875 | |
| 876 if (!ei_one_before_end_p (ei)) | |
| 877 ei_next (&stack[sp - 1]); | |
| 878 else | |
| 879 sp--; | |
| 880 } | |
| 881 } | |
| 882 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
883 /* Detect any infinite loop and activate the kludge. |
| 0 | 884 Note that this doesn't check EXIT_BLOCK itself |
| 885 since EXIT_BLOCK is always added after the outer do-while loop. */ | |
| 886 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 887 if (!TEST_BIT (visited, bb->index)) | |
| 888 { | |
| 889 has_unvisited_bb = true; | |
| 890 | |
| 891 if (EDGE_COUNT (bb->preds) > 0) | |
| 892 { | |
| 893 edge_iterator ei; | |
| 894 edge e; | |
| 895 basic_block visited_pred = NULL; | |
| 896 | |
| 897 /* Find an already visited predecessor. */ | |
| 898 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 899 { | |
| 900 if (TEST_BIT (visited, e->src->index)) | |
| 901 visited_pred = e->src; | |
| 902 } | |
| 903 | |
| 904 if (visited_pred) | |
| 905 { | |
| 906 basic_block be = dfs_find_deadend (bb); | |
| 907 gcc_assert (be != NULL); | |
| 908 SET_BIT (visited, be->index); | |
| 909 stack[sp++] = ei_start (be->preds); | |
| 910 break; | |
| 911 } | |
| 912 } | |
| 913 } | |
| 914 | |
| 915 if (has_unvisited_bb && sp == 0) | |
| 916 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
917 /* No blocks are reachable from EXIT at all. |
| 0 | 918 Find a dead-end from the ENTRY, and restart the iteration. */ |
| 919 basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR); | |
| 920 gcc_assert (be != NULL); | |
| 921 SET_BIT (visited, be->index); | |
| 922 stack[sp++] = ei_start (be->preds); | |
| 923 } | |
| 924 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
925 /* The only case the below while fires is |
| 0 | 926 when there's an infinite loop. */ |
| 927 } | |
| 928 while (sp); | |
| 929 | |
| 930 /* EXIT_BLOCK is always included. */ | |
| 931 post_order[post_order_num++] = EXIT_BLOCK; | |
| 932 | |
| 933 free (stack); | |
| 934 sbitmap_free (visited); | |
| 935 return post_order_num; | |
| 936 } | |
| 937 | |
| 938 /* Compute the depth first search order and store in the array | |
| 939 PRE_ORDER if nonzero, marking the nodes visited in VISITED. If | |
| 940 REV_POST_ORDER is nonzero, return the reverse completion number for each | |
| 941 node. Returns the number of nodes visited. A depth first search | |
| 942 tries to get as far away from the starting point as quickly as | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
943 possible. |
| 0 | 944 |
| 945 pre_order is a really a preorder numbering of the graph. | |
| 946 rev_post_order is really a reverse postorder numbering of the graph. | |
| 947 */ | |
| 948 | |
| 949 int | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
950 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, |
| 0 | 951 bool include_entry_exit) |
| 952 { | |
| 953 edge_iterator *stack; | |
| 954 int sp; | |
| 955 int pre_order_num = 0; | |
| 956 int rev_post_order_num = n_basic_blocks - 1; | |
| 957 sbitmap visited; | |
| 958 | |
| 959 /* Allocate stack for back-tracking up CFG. */ | |
| 960 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
| 961 sp = 0; | |
| 962 | |
| 963 if (include_entry_exit) | |
| 964 { | |
| 965 if (pre_order) | |
| 966 pre_order[pre_order_num] = ENTRY_BLOCK; | |
| 967 pre_order_num++; | |
| 968 if (rev_post_order) | |
| 969 rev_post_order[rev_post_order_num--] = ENTRY_BLOCK; | |
| 970 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
971 else |
| 0 | 972 rev_post_order_num -= NUM_FIXED_BLOCKS; |
| 973 | |
| 974 /* Allocate bitmap to track nodes that have been visited. */ | |
| 975 visited = sbitmap_alloc (last_basic_block); | |
| 976 | |
| 977 /* None of the nodes in the CFG have been visited yet. */ | |
| 978 sbitmap_zero (visited); | |
| 979 | |
| 980 /* Push the first edge on to the stack. */ | |
| 981 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); | |
| 982 | |
| 983 while (sp) | |
| 984 { | |
| 985 edge_iterator ei; | |
| 986 basic_block src; | |
| 987 basic_block dest; | |
| 988 | |
| 989 /* Look at the edge on the top of the stack. */ | |
| 990 ei = stack[sp - 1]; | |
| 991 src = ei_edge (ei)->src; | |
| 992 dest = ei_edge (ei)->dest; | |
| 993 | |
| 994 /* Check if the edge destination has been visited yet. */ | |
| 995 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) | |
| 996 { | |
| 997 /* Mark that we have visited the destination. */ | |
| 998 SET_BIT (visited, dest->index); | |
| 999 | |
| 1000 if (pre_order) | |
| 1001 pre_order[pre_order_num] = dest->index; | |
| 1002 | |
| 1003 pre_order_num++; | |
| 1004 | |
| 1005 if (EDGE_COUNT (dest->succs) > 0) | |
| 1006 /* Since the DEST node has been visited for the first | |
| 1007 time, check its successors. */ | |
| 1008 stack[sp++] = ei_start (dest->succs); | |
| 1009 else if (rev_post_order) | |
| 1010 /* There are no successors for the DEST node so assign | |
| 1011 its reverse completion number. */ | |
| 1012 rev_post_order[rev_post_order_num--] = dest->index; | |
| 1013 } | |
| 1014 else | |
| 1015 { | |
| 1016 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR | |
| 1017 && rev_post_order) | |
| 1018 /* There are no more successors for the SRC node | |
| 1019 so assign its reverse completion number. */ | |
| 1020 rev_post_order[rev_post_order_num--] = src->index; | |
| 1021 | |
| 1022 if (!ei_one_before_end_p (ei)) | |
| 1023 ei_next (&stack[sp - 1]); | |
| 1024 else | |
| 1025 sp--; | |
| 1026 } | |
| 1027 } | |
| 1028 | |
| 1029 free (stack); | |
| 1030 sbitmap_free (visited); | |
| 1031 | |
| 1032 if (include_entry_exit) | |
| 1033 { | |
| 1034 if (pre_order) | |
| 1035 pre_order[pre_order_num] = EXIT_BLOCK; | |
| 1036 pre_order_num++; | |
| 1037 if (rev_post_order) | |
| 1038 rev_post_order[rev_post_order_num--] = EXIT_BLOCK; | |
| 1039 /* The number of nodes visited should be the number of blocks. */ | |
| 1040 gcc_assert (pre_order_num == n_basic_blocks); | |
| 1041 } | |
| 1042 else | |
| 1043 /* The number of nodes visited should be the number of blocks minus | |
| 1044 the entry and exit blocks which are not visited here. */ | |
| 1045 gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS); | |
| 1046 | |
| 1047 return pre_order_num; | |
| 1048 } | |
| 1049 | |
| 1050 /* Compute the depth first search order on the _reverse_ graph and | |
| 1051 store in the array DFS_ORDER, marking the nodes visited in VISITED. | |
| 1052 Returns the number of nodes visited. | |
| 1053 | |
| 1054 The computation is split into three pieces: | |
| 1055 | |
| 1056 flow_dfs_compute_reverse_init () creates the necessary data | |
| 1057 structures. | |
| 1058 | |
| 1059 flow_dfs_compute_reverse_add_bb () adds a basic block to the data | |
| 1060 structures. The block will start the search. | |
| 1061 | |
| 1062 flow_dfs_compute_reverse_execute () continues (or starts) the | |
| 1063 search using the block on the top of the stack, stopping when the | |
| 1064 stack is empty. | |
| 1065 | |
| 1066 flow_dfs_compute_reverse_finish () destroys the necessary data | |
| 1067 structures. | |
| 1068 | |
| 1069 Thus, the user will probably call ..._init(), call ..._add_bb() to | |
| 1070 add a beginning basic block to the stack, call ..._execute(), | |
| 1071 possibly add another bb to the stack and again call ..._execute(), | |
| 1072 ..., and finally call _finish(). */ | |
| 1073 | |
| 1074 /* Initialize the data structures used for depth-first search on the | |
| 1075 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is | |
| 1076 added to the basic block stack. DATA is the current depth-first | |
| 1077 search context. If INITIALIZE_STACK is nonzero, there is an | |
| 1078 element on the stack. */ | |
| 1079 | |
| 1080 static void | |
| 1081 flow_dfs_compute_reverse_init (depth_first_search_ds data) | |
| 1082 { | |
| 1083 /* Allocate stack for back-tracking up CFG. */ | |
| 1084 data->stack = XNEWVEC (basic_block, n_basic_blocks); | |
| 1085 data->sp = 0; | |
| 1086 | |
| 1087 /* Allocate bitmap to track nodes that have been visited. */ | |
| 1088 data->visited_blocks = sbitmap_alloc (last_basic_block); | |
| 1089 | |
| 1090 /* None of the nodes in the CFG have been visited yet. */ | |
| 1091 sbitmap_zero (data->visited_blocks); | |
| 1092 | |
| 1093 return; | |
| 1094 } | |
| 1095 | |
| 1096 /* Add the specified basic block to the top of the dfs data | |
| 1097 structures. When the search continues, it will start at the | |
| 1098 block. */ | |
| 1099 | |
| 1100 static void | |
| 1101 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb) | |
| 1102 { | |
| 1103 data->stack[data->sp++] = bb; | |
| 1104 SET_BIT (data->visited_blocks, bb->index); | |
| 1105 } | |
| 1106 | |
| 1107 /* Continue the depth-first search through the reverse graph starting with the | |
| 1108 block at the stack's top and ending when the stack is empty. Visited nodes | |
| 1109 are marked. Returns an unvisited basic block, or NULL if there is none | |
| 1110 available. */ | |
| 1111 | |
| 1112 static basic_block | |
| 1113 flow_dfs_compute_reverse_execute (depth_first_search_ds data, | |
| 1114 basic_block last_unvisited) | |
| 1115 { | |
| 1116 basic_block bb; | |
| 1117 edge e; | |
| 1118 edge_iterator ei; | |
| 1119 | |
| 1120 while (data->sp > 0) | |
| 1121 { | |
| 1122 bb = data->stack[--data->sp]; | |
| 1123 | |
| 1124 /* Perform depth-first search on adjacent vertices. */ | |
| 1125 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1126 if (!TEST_BIT (data->visited_blocks, e->src->index)) | |
| 1127 flow_dfs_compute_reverse_add_bb (data, e->src); | |
| 1128 } | |
| 1129 | |
| 1130 /* Determine if there are unvisited basic blocks. */ | |
| 1131 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) | |
| 1132 if (!TEST_BIT (data->visited_blocks, bb->index)) | |
| 1133 return bb; | |
| 1134 | |
| 1135 return NULL; | |
| 1136 } | |
| 1137 | |
| 1138 /* Destroy the data structures needed for depth-first search on the | |
| 1139 reverse graph. */ | |
| 1140 | |
| 1141 static void | |
| 1142 flow_dfs_compute_reverse_finish (depth_first_search_ds data) | |
| 1143 { | |
| 1144 free (data->stack); | |
| 1145 sbitmap_free (data->visited_blocks); | |
| 1146 } | |
| 1147 | |
| 1148 /* Performs dfs search from BB over vertices satisfying PREDICATE; | |
| 1149 if REVERSE, go against direction of edges. Returns number of blocks | |
| 1150 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ | |
| 1151 int | |
| 1152 dfs_enumerate_from (basic_block bb, int reverse, | |
| 1153 bool (*predicate) (const_basic_block, const void *), | |
| 1154 basic_block *rslt, int rslt_max, const void *data) | |
| 1155 { | |
| 1156 basic_block *st, lbb; | |
| 1157 int sp = 0, tv = 0; | |
| 1158 unsigned size; | |
| 1159 | |
| 1160 /* A bitmap to keep track of visited blocks. Allocating it each time | |
| 1161 this function is called is not possible, since dfs_enumerate_from | |
| 1162 is often used on small (almost) disjoint parts of cfg (bodies of | |
| 1163 loops), and allocating a large sbitmap would lead to quadratic | |
| 1164 behavior. */ | |
| 1165 static sbitmap visited; | |
| 1166 static unsigned v_size; | |
| 1167 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1168 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1169 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1170 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index)) |
| 0 | 1171 |
| 1172 /* Resize the VISITED sbitmap if necessary. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1173 size = last_basic_block; |
| 0 | 1174 if (size < 10) |
| 1175 size = 10; | |
| 1176 | |
| 1177 if (!visited) | |
| 1178 { | |
| 1179 | |
| 1180 visited = sbitmap_alloc (size); | |
| 1181 sbitmap_zero (visited); | |
| 1182 v_size = size; | |
| 1183 } | |
| 1184 else if (v_size < size) | |
| 1185 { | |
| 1186 /* Ensure that we increase the size of the sbitmap exponentially. */ | |
| 1187 if (2 * v_size > size) | |
| 1188 size = 2 * v_size; | |
| 1189 | |
| 1190 visited = sbitmap_resize (visited, size, 0); | |
| 1191 v_size = size; | |
| 1192 } | |
| 1193 | |
| 1194 st = XCNEWVEC (basic_block, rslt_max); | |
| 1195 rslt[tv++] = st[sp++] = bb; | |
| 1196 MARK_VISITED (bb); | |
| 1197 while (sp) | |
| 1198 { | |
| 1199 edge e; | |
| 1200 edge_iterator ei; | |
| 1201 lbb = st[--sp]; | |
| 1202 if (reverse) | |
| 1203 { | |
| 1204 FOR_EACH_EDGE (e, ei, lbb->preds) | |
| 1205 if (!VISITED_P (e->src) && predicate (e->src, data)) | |
| 1206 { | |
| 1207 gcc_assert (tv != rslt_max); | |
| 1208 rslt[tv++] = st[sp++] = e->src; | |
| 1209 MARK_VISITED (e->src); | |
| 1210 } | |
| 1211 } | |
| 1212 else | |
| 1213 { | |
| 1214 FOR_EACH_EDGE (e, ei, lbb->succs) | |
| 1215 if (!VISITED_P (e->dest) && predicate (e->dest, data)) | |
| 1216 { | |
| 1217 gcc_assert (tv != rslt_max); | |
| 1218 rslt[tv++] = st[sp++] = e->dest; | |
| 1219 MARK_VISITED (e->dest); | |
| 1220 } | |
| 1221 } | |
| 1222 } | |
| 1223 free (st); | |
| 1224 for (sp = 0; sp < tv; sp++) | |
| 1225 UNMARK_VISITED (rslt[sp]); | |
| 1226 return tv; | |
| 1227 #undef MARK_VISITED | |
| 1228 #undef UNMARK_VISITED | |
| 1229 #undef VISITED_P | |
| 1230 } | |
| 1231 | |
| 1232 | |
| 1233 /* Compute dominance frontiers, ala Harvey, Ferrante, et al. | |
| 1234 | |
| 1235 This algorithm can be found in Timothy Harvey's PhD thesis, at | |
| 1236 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative | |
| 1237 dominance algorithms. | |
| 1238 | |
| 1239 First, we identify each join point, j (any node with more than one | |
| 1240 incoming edge is a join point). | |
| 1241 | |
| 1242 We then examine each predecessor, p, of j and walk up the dominator tree | |
| 1243 starting at p. | |
| 1244 | |
| 1245 We stop the walk when we reach j's immediate dominator - j is in the | |
| 1246 dominance frontier of each of the nodes in the walk, except for j's | |
| 1247 immediate dominator. Intuitively, all of the rest of j's dominators are | |
| 1248 shared by j's predecessors as well. | |
| 1249 Since they dominate j, they will not have j in their dominance frontiers. | |
| 1250 | |
| 1251 The number of nodes touched by this algorithm is equal to the size | |
| 1252 of the dominance frontiers, no more, no less. | |
| 1253 */ | |
| 1254 | |
| 1255 | |
| 1256 static void | |
| 1257 compute_dominance_frontiers_1 (bitmap *frontiers) | |
| 1258 { | |
| 1259 edge p; | |
| 1260 edge_iterator ei; | |
| 1261 basic_block b; | |
| 1262 FOR_EACH_BB (b) | |
| 1263 { | |
| 1264 if (EDGE_COUNT (b->preds) >= 2) | |
| 1265 { | |
| 1266 FOR_EACH_EDGE (p, ei, b->preds) | |
| 1267 { | |
| 1268 basic_block runner = p->src; | |
| 1269 basic_block domsb; | |
| 1270 if (runner == ENTRY_BLOCK_PTR) | |
| 1271 continue; | |
| 1272 | |
| 1273 domsb = get_immediate_dominator (CDI_DOMINATORS, b); | |
| 1274 while (runner != domsb) | |
| 1275 { | |
| 1276 if (bitmap_bit_p (frontiers[runner->index], b->index)) | |
| 1277 break; | |
| 1278 bitmap_set_bit (frontiers[runner->index], | |
| 1279 b->index); | |
| 1280 runner = get_immediate_dominator (CDI_DOMINATORS, | |
| 1281 runner); | |
| 1282 } | |
| 1283 } | |
| 1284 } | |
| 1285 } | |
| 1286 } | |
| 1287 | |
| 1288 | |
| 1289 void | |
| 1290 compute_dominance_frontiers (bitmap *frontiers) | |
| 1291 { | |
| 1292 timevar_push (TV_DOM_FRONTIERS); | |
| 1293 | |
| 1294 compute_dominance_frontiers_1 (frontiers); | |
| 1295 | |
| 1296 timevar_pop (TV_DOM_FRONTIERS); | |
| 1297 } | |
| 1298 | |
| 1299 /* Given a set of blocks with variable definitions (DEF_BLOCKS), | |
| 1300 return a bitmap with all the blocks in the iterated dominance | |
| 1301 frontier of the blocks in DEF_BLOCKS. DFS contains dominance | |
| 1302 frontier information as returned by compute_dominance_frontiers. | |
| 1303 | |
| 1304 The resulting set of blocks are the potential sites where PHI nodes | |
| 1305 are needed. The caller is responsible for freeing the memory | |
| 1306 allocated for the return value. */ | |
| 1307 | |
| 1308 bitmap | |
| 1309 compute_idf (bitmap def_blocks, bitmap *dfs) | |
| 1310 { | |
| 1311 bitmap_iterator bi; | |
| 1312 unsigned bb_index, i; | |
| 1313 VEC(int,heap) *work_stack; | |
| 1314 bitmap phi_insertion_points; | |
| 1315 | |
| 1316 work_stack = VEC_alloc (int, heap, n_basic_blocks); | |
| 1317 phi_insertion_points = BITMAP_ALLOC (NULL); | |
| 1318 | |
| 1319 /* Seed the work list with all the blocks in DEF_BLOCKS. We use | |
| 1320 VEC_quick_push here for speed. This is safe because we know that | |
| 1321 the number of definition blocks is no greater than the number of | |
| 1322 basic blocks, which is the initial capacity of WORK_STACK. */ | |
| 1323 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi) | |
| 1324 VEC_quick_push (int, work_stack, bb_index); | |
| 1325 | |
| 1326 /* Pop a block off the worklist, add every block that appears in | |
| 1327 the original block's DF that we have not already processed to | |
| 1328 the worklist. Iterate until the worklist is empty. Blocks | |
| 1329 which are added to the worklist are potential sites for | |
| 1330 PHI nodes. */ | |
| 1331 while (VEC_length (int, work_stack) > 0) | |
| 1332 { | |
| 1333 bb_index = VEC_pop (int, work_stack); | |
| 1334 | |
| 1335 /* Since the registration of NEW -> OLD name mappings is done | |
| 1336 separately from the call to update_ssa, when updating the SSA | |
| 1337 form, the basic blocks where new and/or old names are defined | |
| 1338 may have disappeared by CFG cleanup calls. In this case, | |
| 1339 we may pull a non-existing block from the work stack. */ | |
| 1340 gcc_assert (bb_index < (unsigned) last_basic_block); | |
| 1341 | |
| 1342 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points, | |
| 1343 0, i, bi) | |
| 1344 { | |
| 1345 /* Use a safe push because if there is a definition of VAR | |
| 1346 in every basic block, then WORK_STACK may eventually have | |
| 1347 more than N_BASIC_BLOCK entries. */ | |
| 1348 VEC_safe_push (int, heap, work_stack, i); | |
| 1349 bitmap_set_bit (phi_insertion_points, i); | |
| 1350 } | |
| 1351 } | |
| 1352 | |
| 1353 VEC_free (int, heap, work_stack); | |
| 1354 | |
| 1355 return phi_insertion_points; | |
| 1356 } | |
| 1357 | |
| 1358 |