Mercurial > hg > CbC > CbC_gcc
annotate gcc/domwalk.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | a06113de4d67 |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Generic dominator tree walker |
| 2 Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, | |
| 3 Inc. | |
| 4 Contributed by Diego Novillo <dnovillo@redhat.com> | |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify | |
| 9 it under the terms of the GNU General Public License as published by | |
| 10 the Free Software Foundation; either version 3, or (at your option) | |
| 11 any later version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, | |
| 14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 16 GNU General Public License 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 #include "config.h" | |
| 23 #include "system.h" | |
| 24 #include "coretypes.h" | |
| 25 #include "tm.h" | |
| 26 #include "basic-block.h" | |
| 27 #include "domwalk.h" | |
| 28 #include "ggc.h" | |
| 29 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
30 /* This file implements a generic walker for dominator trees. |
| 0 | 31 |
| 32 To understand the dominator walker one must first have a grasp of dominators, | |
| 33 immediate dominators and the dominator tree. | |
| 34 | |
| 35 Dominators | |
| 36 A block B1 is said to dominate B2 if every path from the entry to B2 must | |
| 37 pass through B1. Given the dominance relationship, we can proceed to | |
| 38 compute immediate dominators. Note it is not important whether or not | |
| 39 our definition allows a block to dominate itself. | |
| 40 | |
| 41 Immediate Dominators: | |
| 42 Every block in the CFG has no more than one immediate dominator. The | |
| 43 immediate dominator of block BB must dominate BB and must not dominate | |
| 44 any other dominator of BB and must not be BB itself. | |
| 45 | |
| 46 Dominator tree: | |
| 47 If we then construct a tree where each node is a basic block and there | |
| 48 is an edge from each block's immediate dominator to the block itself, then | |
| 49 we have a dominator tree. | |
| 50 | |
| 51 | |
| 52 [ Note this walker can also walk the post-dominator tree, which is | |
| 53 defined in a similar manner. i.e., block B1 is said to post-dominate | |
| 54 block B2 if all paths from B2 to the exit block must pass through | |
| 55 B1. ] | |
| 56 | |
| 57 For example, given the CFG | |
| 58 | |
| 59 1 | |
| 60 | | |
| 61 2 | |
| 62 / \ | |
| 63 3 4 | |
| 64 / \ | |
| 65 +---------->5 6 | |
| 66 | / \ / | |
| 67 | +--->8 7 | |
| 68 | | / | | |
| 69 | +--9 11 | |
| 70 | / | | |
| 71 +--- 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
|
72 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
73 |
| 0 | 74 We have a dominator tree which looks like |
| 75 | |
| 76 1 | |
| 77 | | |
| 78 2 | |
| 79 / \ | |
| 80 / \ | |
| 81 3 4 | |
| 82 / / \ \ | |
| 83 | | | | | |
| 84 5 6 7 12 | |
| 85 | | | |
| 86 8 11 | |
| 87 | | |
| 88 9 | |
| 89 | | |
| 90 10 | |
|
55
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 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
93 |
| 0 | 94 The dominator tree is the basis for a number of analysis, transformation |
| 95 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
|
96 |
| 0 | 97 The dominator walker is a generic routine which visits blocks in the CFG |
| 98 via a depth first search of the dominator tree. In the example above | |
| 99 the dominator walker might visit blocks in the following order | |
| 100 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
|
101 |
| 0 | 102 The dominator walker has a number of callbacks to perform actions |
| 103 during the walk of the dominator tree. There are two callbacks | |
| 104 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
|
105 one after visiting the dominator children. There is a callback |
| 0 | 106 before and after each statement walk callback. In addition, the |
| 107 dominator walker manages allocation/deallocation of data structures | |
| 108 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
|
109 |
| 0 | 110 The dominator walker is meant to provide a generic means to build a pass |
| 111 which can analyze or transform/optimize a function based on walking | |
| 112 the dominator tree. One simply fills in the dominator walker data | |
| 113 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
|
114 |
| 0 | 115 We currently use the dominator walker to prune the set of variables |
| 116 which might need PHI nodes (which can greatly improve compile-time | |
| 117 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
|
118 |
| 0 | 119 We also use the dominator walker to rewrite the function into SSA form |
| 120 which reduces code duplication since the rewriting phase is inherently | |
| 121 a walk of the dominator tree. | |
| 122 | |
| 123 And (of course), we use the dominator walker to drive our dominator | |
| 124 optimizer, which is a semi-global optimizer. | |
| 125 | |
| 126 TODO: | |
| 127 | |
| 128 Walking statements is based on the block statement iterator abstraction, | |
| 129 which is currently an abstraction over walking tree statements. Thus | |
| 130 the dominator walker is currently only useful for trees. */ | |
| 131 | |
| 132 /* Recursively walk the dominator tree. | |
| 133 | |
| 134 WALK_DATA contains a set of callbacks to perform pass-specific | |
| 135 actions during the dominator walk as well as a stack of block local | |
| 136 data maintained during the dominator walk. | |
| 137 | |
| 138 BB is the basic block we are currently visiting. */ | |
| 139 | |
| 140 void | |
| 141 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) | |
| 142 { | |
| 143 void *bd = NULL; | |
| 144 basic_block dest; | |
| 145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); | |
| 146 int sp = 0; | |
| 147 | |
| 148 while (true) | |
| 149 { | |
| 150 /* Don't worry about unreachable blocks. */ | |
| 151 if (EDGE_COUNT (bb->preds) > 0 | |
| 152 || bb == ENTRY_BLOCK_PTR | |
| 153 || bb == EXIT_BLOCK_PTR) | |
| 154 { | |
| 155 /* Callback to initialize the local data structure. */ | |
| 156 if (walk_data->initialize_block_local_data) | |
| 157 { | |
| 158 bool recycled; | |
| 159 | |
| 160 /* First get some local data, reusing any local data | |
| 161 pointer we may have saved. */ | |
| 162 if (VEC_length (void_p, walk_data->free_block_data) > 0) | |
| 163 { | |
| 164 bd = VEC_pop (void_p, walk_data->free_block_data); | |
| 165 recycled = 1; | |
| 166 } | |
| 167 else | |
| 168 { | |
| 169 bd = xcalloc (1, walk_data->block_local_data_size); | |
| 170 recycled = 0; | |
| 171 } | |
| 172 | |
| 173 /* Push the local data into the local data stack. */ | |
| 174 VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd); | |
| 175 | |
| 176 /* Call the initializer. */ | |
| 177 walk_data->initialize_block_local_data (walk_data, bb, | |
| 178 recycled); | |
| 179 | |
| 180 } | |
| 181 | |
| 182 /* Callback for operations to execute before we have walked the | |
| 183 dominator children, but before we walk statements. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 if (walk_data->before_dom_children) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 (*walk_data->before_dom_children) (walk_data, bb); |
| 0 | 186 |
| 187 /* Mark the current BB to be popped out of the recursion stack | |
| 188 once children are processed. */ | |
| 189 worklist[sp++] = bb; | |
| 190 worklist[sp++] = NULL; | |
| 191 | |
| 192 for (dest = first_dom_son (walk_data->dom_direction, bb); | |
| 193 dest; dest = next_dom_son (walk_data->dom_direction, dest)) | |
| 194 worklist[sp++] = dest; | |
| 195 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
196 /* NULL is used to mark pop operations in the recursion stack. */ |
| 0 | 197 while (sp > 0 && !worklist[sp - 1]) |
| 198 { | |
| 199 --sp; | |
| 200 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
|
201 |
| 0 | 202 /* Callback for operations to execute after we have walked the |
| 203 dominator children, but before we walk statements. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
204 if (walk_data->after_dom_children) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 (*walk_data->after_dom_children) (walk_data, bb); |
| 0 | 206 |
| 207 if (walk_data->initialize_block_local_data) | |
| 208 { | |
| 209 /* And finally pop the record off the block local data stack. */ | |
| 210 bd = VEC_pop (void_p, walk_data->block_data_stack); | |
| 211 /* And save the block data so that we can re-use it. */ | |
| 212 VEC_safe_push (void_p, heap, walk_data->free_block_data, bd); | |
| 213 } | |
| 214 } | |
| 215 if (sp) | |
| 216 bb = worklist[--sp]; | |
| 217 else | |
| 218 break; | |
| 219 } | |
| 220 free (worklist); | |
| 221 } | |
| 222 | |
| 223 void | |
| 224 init_walk_dominator_tree (struct dom_walk_data *walk_data) | |
| 225 { | |
| 226 walk_data->free_block_data = NULL; | |
| 227 walk_data->block_data_stack = NULL; | |
| 228 } | |
| 229 | |
| 230 void | |
| 231 fini_walk_dominator_tree (struct dom_walk_data *walk_data) | |
| 232 { | |
| 233 if (walk_data->initialize_block_local_data) | |
| 234 { | |
| 235 while (VEC_length (void_p, walk_data->free_block_data) > 0) | |
| 236 free (VEC_pop (void_p, walk_data->free_block_data)); | |
| 237 } | |
| 238 | |
| 239 VEC_free (void_p, heap, walk_data->free_block_data); | |
| 240 VEC_free (void_p, heap, walk_data->block_data_stack); | |
| 241 } |