Mercurial > hg > CbC > CbC_gcc
annotate gcc/domwalk.c @ 111:04ced10e8804
gcc 7
| author | kono |
|---|---|
| date | Fri, 27 Oct 2017 22:46:09 +0900 |
| parents | f6334be47118 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* Generic dominator tree walker |
| 111 | 2 Copyright (C) 2003-2017 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Diego Novillo <dnovillo@redhat.com> |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 #include "config.h" | |
| 22 #include "system.h" | |
| 23 #include "coretypes.h" | |
| 111 | 24 #include "backend.h" |
| 25 #include "cfganal.h" | |
| 0 | 26 #include "domwalk.h" |
| 111 | 27 #include "dumpfile.h" |
| 0 | 28 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
29 /* This file implements a generic walker for dominator trees. |
| 0 | 30 |
| 31 To understand the dominator walker one must first have a grasp of dominators, | |
| 32 immediate dominators and the dominator tree. | |
| 33 | |
| 34 Dominators | |
| 35 A block B1 is said to dominate B2 if every path from the entry to B2 must | |
| 36 pass through B1. Given the dominance relationship, we can proceed to | |
| 37 compute immediate dominators. Note it is not important whether or not | |
| 38 our definition allows a block to dominate itself. | |
| 39 | |
| 40 Immediate Dominators: | |
| 41 Every block in the CFG has no more than one immediate dominator. The | |
| 42 immediate dominator of block BB must dominate BB and must not dominate | |
| 43 any other dominator of BB and must not be BB itself. | |
| 44 | |
| 45 Dominator tree: | |
| 46 If we then construct a tree where each node is a basic block and there | |
| 47 is an edge from each block's immediate dominator to the block itself, then | |
| 48 we have a dominator tree. | |
| 49 | |
| 50 | |
| 51 [ Note this walker can also walk the post-dominator tree, which is | |
| 52 defined in a similar manner. i.e., block B1 is said to post-dominate | |
| 53 block B2 if all paths from B2 to the exit block must pass through | |
| 54 B1. ] | |
| 55 | |
| 56 For example, given the CFG | |
| 57 | |
| 58 1 | |
| 59 | | |
| 60 2 | |
| 61 / \ | |
| 62 3 4 | |
| 63 / \ | |
| 64 +---------->5 6 | |
| 65 | / \ / | |
| 66 | +--->8 7 | |
| 67 | | / | | |
| 68 | +--9 11 | |
| 69 | / | | |
| 70 +--- 10 ---> 12 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
71 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
72 |
| 0 | 73 We have a dominator tree which looks like |
| 74 | |
| 75 1 | |
| 76 | | |
| 77 2 | |
| 78 / \ | |
| 79 / \ | |
| 80 3 4 | |
| 81 / / \ \ | |
| 82 | | | | | |
| 83 5 6 7 12 | |
| 84 | | | |
| 85 8 11 | |
| 86 | | |
| 87 9 | |
| 88 | | |
| 89 10 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
92 |
| 0 | 93 The dominator tree is the basis for a number of analysis, transformation |
| 94 and optimization algorithms that operate on a semi-global basis. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
95 |
| 0 | 96 The dominator walker is a generic routine which visits blocks in the CFG |
| 97 via a depth first search of the dominator tree. In the example above | |
| 98 the dominator walker might visit blocks in the following order | |
| 99 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
100 |
| 0 | 101 The dominator walker has a number of callbacks to perform actions |
| 102 during the walk of the dominator tree. There are two callbacks | |
| 103 which walk statements, one before visiting the dominator children, | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
104 one after visiting the dominator children. There is a callback |
| 0 | 105 before and after each statement walk callback. In addition, the |
| 106 dominator walker manages allocation/deallocation of data structures | |
| 107 which are local to each block visited. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 |
| 0 | 109 The dominator walker is meant to provide a generic means to build a pass |
| 110 which can analyze or transform/optimize a function based on walking | |
| 111 the dominator tree. One simply fills in the dominator walker data | |
| 112 structure with the appropriate callbacks and calls the walker. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 |
| 0 | 114 We currently use the dominator walker to prune the set of variables |
| 115 which might need PHI nodes (which can greatly improve compile-time | |
| 116 performance in some cases). | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
117 |
| 0 | 118 We also use the dominator walker to rewrite the function into SSA form |
| 119 which reduces code duplication since the rewriting phase is inherently | |
| 120 a walk of the dominator tree. | |
| 121 | |
| 122 And (of course), we use the dominator walker to drive our dominator | |
| 123 optimizer, which is a semi-global optimizer. | |
| 124 | |
| 125 TODO: | |
| 126 | |
| 127 Walking statements is based on the block statement iterator abstraction, | |
| 128 which is currently an abstraction over walking tree statements. Thus | |
| 129 the dominator walker is currently only useful for trees. */ | |
| 130 | |
| 111 | 131 /* Reverse postorder index of each basic block. */ |
| 132 static int *bb_postorder; | |
| 133 | |
| 134 static int | |
| 135 cmp_bb_postorder (const void *a, const void *b) | |
| 136 { | |
| 137 basic_block bb1 = *(const basic_block *)(a); | |
| 138 basic_block bb2 = *(const basic_block *)(b); | |
| 139 /* Place higher completion number first (pop off lower number first). */ | |
| 140 return bb_postorder[bb2->index] - bb_postorder[bb1->index]; | |
| 141 } | |
| 142 | |
| 143 /* Permute array BBS of N basic blocks in postorder, | |
| 144 i.e. by descending number in BB_POSTORDER array. */ | |
| 145 | |
| 146 static void | |
| 147 sort_bbs_postorder (basic_block *bbs, int n) | |
| 148 { | |
| 149 if (__builtin_expect (n == 2, true)) | |
| 150 { | |
| 151 basic_block bb0 = bbs[0], bb1 = bbs[1]; | |
| 152 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
| 153 bbs[0] = bb1, bbs[1] = bb0; | |
| 154 } | |
| 155 else if (__builtin_expect (n == 3, true)) | |
| 156 { | |
| 157 basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2]; | |
| 158 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
| 159 std::swap (bb0, bb1); | |
| 160 if (bb_postorder[bb1->index] < bb_postorder[bb2->index]) | |
| 161 { | |
| 162 std::swap (bb1, bb2); | |
| 163 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
| 164 std::swap (bb0, bb1); | |
| 165 } | |
| 166 bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2; | |
| 167 } | |
| 168 else | |
| 169 qsort (bbs, n, sizeof *bbs, cmp_bb_postorder); | |
| 170 } | |
| 171 | |
| 172 /* Constructor for a dom walker. | |
| 173 | |
| 174 If SKIP_UNREACHBLE_BLOCKS is true, then we need to set | |
| 175 EDGE_EXECUTABLE on every edge in the CFG. */ | |
| 176 dom_walker::dom_walker (cdi_direction direction, | |
| 177 bool skip_unreachable_blocks, | |
| 178 int *bb_index_to_rpo) | |
| 179 : m_dom_direction (direction), | |
| 180 m_skip_unreachable_blocks (skip_unreachable_blocks), | |
| 181 m_user_bb_to_rpo (bb_index_to_rpo != NULL), | |
| 182 m_unreachable_dom (NULL), | |
| 183 m_bb_to_rpo (bb_index_to_rpo) | |
| 184 { | |
| 185 /* Compute the basic-block index to RPO mapping if not provided by | |
| 186 the user. */ | |
| 187 if (! m_bb_to_rpo && direction == CDI_DOMINATORS) | |
| 188 { | |
| 189 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
| 190 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, | |
| 191 true); | |
| 192 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); | |
| 193 for (int i = 0; i < postorder_num; ++i) | |
| 194 m_bb_to_rpo[postorder[i]] = i; | |
| 195 free (postorder); | |
| 196 } | |
| 197 | |
| 198 /* If we are not skipping unreachable blocks, then there is nothing | |
| 199 further to do. */ | |
| 200 if (!m_skip_unreachable_blocks) | |
| 201 return; | |
| 0 | 202 |
| 111 | 203 basic_block bb; |
| 204 FOR_ALL_BB_FN (bb, cfun) | |
| 205 { | |
| 206 edge_iterator ei; | |
| 207 edge e; | |
| 208 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 209 e->flags |= EDGE_EXECUTABLE; | |
| 210 } | |
| 211 } | |
| 212 | |
| 213 /* Destructor. */ | |
| 214 | |
| 215 dom_walker::~dom_walker () | |
| 216 { | |
| 217 if (! m_user_bb_to_rpo) | |
| 218 free (m_bb_to_rpo); | |
| 219 } | |
| 220 | |
| 221 /* Return TRUE if BB is reachable, false otherwise. */ | |
| 222 | |
| 223 bool | |
| 224 dom_walker::bb_reachable (struct function *fun, basic_block bb) | |
| 225 { | |
| 226 /* If we're not skipping unreachable blocks, then assume everything | |
| 227 is reachable. */ | |
| 228 if (!m_skip_unreachable_blocks) | |
| 229 return true; | |
| 0 | 230 |
| 111 | 231 /* If any of the predecessor edges that do not come from blocks dominated |
| 232 by us are still marked as possibly executable consider this block | |
| 233 reachable. */ | |
| 234 bool reachable = false; | |
| 235 if (!m_unreachable_dom) | |
| 236 { | |
| 237 reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun); | |
| 238 edge_iterator ei; | |
| 239 edge e; | |
| 240 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 241 if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
| 242 reachable |= (e->flags & EDGE_EXECUTABLE); | |
| 243 } | |
| 244 | |
| 245 return reachable; | |
| 246 } | |
| 247 | |
| 248 /* BB has been determined to be unreachable. Propagate that property | |
| 249 to incoming and outgoing edges of BB as appropriate. */ | |
| 250 | |
| 251 void | |
| 252 dom_walker::propagate_unreachable_to_edges (basic_block bb, | |
| 253 FILE *dump_file, | |
| 254 dump_flags_t dump_flags) | |
| 255 { | |
| 256 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 257 fprintf (dump_file, "Marking all outgoing edges of unreachable " | |
| 258 "BB %d as not executable\n", bb->index); | |
| 259 | |
| 260 edge_iterator ei; | |
| 261 edge e; | |
| 262 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 263 e->flags &= ~EDGE_EXECUTABLE; | |
| 264 | |
| 265 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 266 { | |
| 267 if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
| 268 { | |
| 269 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 270 fprintf (dump_file, "Marking backedge from BB %d into " | |
| 271 "unreachable BB %d as not executable\n", | |
| 272 e->src->index, bb->index); | |
| 273 e->flags &= ~EDGE_EXECUTABLE; | |
| 274 } | |
| 275 } | |
| 276 | |
| 277 if (!m_unreachable_dom) | |
| 278 m_unreachable_dom = bb; | |
| 279 } | |
| 280 | |
| 281 const edge dom_walker::STOP = (edge)-1; | |
| 282 | |
| 283 /* Recursively walk the dominator tree. | |
| 0 | 284 BB is the basic block we are currently visiting. */ |
| 285 | |
| 286 void | |
| 111 | 287 dom_walker::walk (basic_block bb) |
| 0 | 288 { |
| 289 basic_block dest; | |
| 111 | 290 basic_block *worklist = XNEWVEC (basic_block, |
| 291 n_basic_blocks_for_fn (cfun) * 2); | |
| 0 | 292 int sp = 0; |
| 111 | 293 bb_postorder = m_bb_to_rpo; |
| 0 | 294 |
| 295 while (true) | |
| 296 { | |
| 297 /* Don't worry about unreachable blocks. */ | |
| 298 if (EDGE_COUNT (bb->preds) > 0 | |
| 111 | 299 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| 300 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
| 0 | 301 { |
| 111 | 302 edge taken_edge = NULL; |
| 0 | 303 |
| 111 | 304 /* Callback for subclasses to do custom things before we have walked |
| 305 the dominator children, but before we walk statements. */ | |
| 306 if (this->bb_reachable (cfun, bb)) | |
| 307 { | |
| 308 taken_edge = before_dom_children (bb); | |
| 309 if (taken_edge && taken_edge != STOP) | |
| 0 | 310 { |
| 111 | 311 edge_iterator ei; |
| 312 edge e; | |
| 313 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 314 if (e != taken_edge) | |
| 315 e->flags &= ~EDGE_EXECUTABLE; | |
| 0 | 316 } |
| 317 } | |
| 111 | 318 else |
| 319 propagate_unreachable_to_edges (bb, dump_file, dump_flags); | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
320 |
| 0 | 321 /* Mark the current BB to be popped out of the recursion stack |
| 322 once children are processed. */ | |
| 323 worklist[sp++] = bb; | |
| 324 worklist[sp++] = NULL; | |
| 325 | |
| 111 | 326 /* If the callback returned NONE then we are supposed to |
| 327 stop and not even propagate EDGE_EXECUTABLE further. */ | |
| 328 if (taken_edge != STOP) | |
| 329 { | |
| 330 int saved_sp = sp; | |
| 331 for (dest = first_dom_son (m_dom_direction, bb); | |
| 332 dest; dest = next_dom_son (m_dom_direction, dest)) | |
| 333 worklist[sp++] = dest; | |
| 334 if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS) | |
| 335 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); | |
| 336 } | |
| 0 | 337 } |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
338 /* NULL is used to mark pop operations in the recursion stack. */ |
| 0 | 339 while (sp > 0 && !worklist[sp - 1]) |
| 340 { | |
| 341 --sp; | |
| 342 bb = worklist[--sp]; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
343 |
| 111 | 344 /* Callback allowing subclasses to do custom things after we have |
| 345 walked dominator children, but before we walk statements. */ | |
| 346 if (bb_reachable (cfun, bb)) | |
| 347 after_dom_children (bb); | |
| 348 else if (m_unreachable_dom == bb) | |
| 349 m_unreachable_dom = NULL; | |
| 0 | 350 } |
| 351 if (sp) | |
| 111 | 352 bb = worklist[--sp]; |
| 0 | 353 else |
| 354 break; | |
| 355 } | |
| 111 | 356 bb_postorder = NULL; |
| 0 | 357 free (worklist); |
| 358 } |