Mercurial > hg > CbC > CbC_gcc

comparison gcc/domwalk.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
21 21
22 #include "config.h" 22 #include "config.h"
23 #include "system.h" 23 #include "system.h"
24 #include "coretypes.h" 24 #include "coretypes.h"
25 #include "tm.h" 25 #include "tm.h"
26 #include "tree.h"
27 #include "basic-block.h" 26 #include "basic-block.h"
28 #include "tree-flow.h"
29 #include "domwalk.h" 27 #include "domwalk.h"
30 #include "ggc.h" 28 #include "ggc.h"
31 29
32 /* This file implements a generic walker for dominator trees. 30 /* This file implements a generic walker for dominator trees.
33 31
34 To understand the dominator walker one must first have a grasp of dominators, 32 To understand the dominator walker one must first have a grasp of dominators,
35 immediate dominators and the dominator tree. 33 immediate dominators and the dominator tree.
36 34
37 Dominators 35 Dominators
69 | +--->8 7 67 | +--->8 7
70 | | / | 68 | | / |
71 | +--9 11 69 | +--9 11
72 | / | 70 | / |
73 +--- 10 ---> 12 71 +--- 10 ---> 12
74 72
75 73
76 We have a dominator tree which looks like 74 We have a dominator tree which looks like
77 75
78 1 76 1
79 | 77 |
80 2 78 2
88 8 11 86 8 11
89 | 87 |
90 9 88 9
91 | 89 |
92 10 90 10
93 91
94 92
95 93
96 The dominator tree is the basis for a number of analysis, transformation 94 The dominator tree is the basis for a number of analysis, transformation
97 and optimization algorithms that operate on a semi-global basis. 95 and optimization algorithms that operate on a semi-global basis.
98 96
99 The dominator walker is a generic routine which visits blocks in the CFG 97 The dominator walker is a generic routine which visits blocks in the CFG
100 via a depth first search of the dominator tree. In the example above 98 via a depth first search of the dominator tree. In the example above
101 the dominator walker might visit blocks in the following order 99 the dominator walker might visit blocks in the following order
102 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. 100 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12.
103 101
104 The dominator walker has a number of callbacks to perform actions 102 The dominator walker has a number of callbacks to perform actions
105 during the walk of the dominator tree. There are two callbacks 103 during the walk of the dominator tree. There are two callbacks
106 which walk statements, one before visiting the dominator children, 104 which walk statements, one before visiting the dominator children,
107 one after visiting the dominator children. There is a callback 105 one after visiting the dominator children. There is a callback
108 before and after each statement walk callback. In addition, the 106 before and after each statement walk callback. In addition, the
109 dominator walker manages allocation/deallocation of data structures 107 dominator walker manages allocation/deallocation of data structures
110 which are local to each block visited. 108 which are local to each block visited.
111 109
112 The dominator walker is meant to provide a generic means to build a pass 110 The dominator walker is meant to provide a generic means to build a pass
113 which can analyze or transform/optimize a function based on walking 111 which can analyze or transform/optimize a function based on walking
114 the dominator tree. One simply fills in the dominator walker data 112 the dominator tree. One simply fills in the dominator walker data
115 structure with the appropriate callbacks and calls the walker. 113 structure with the appropriate callbacks and calls the walker.
116 114
117 We currently use the dominator walker to prune the set of variables 115 We currently use the dominator walker to prune the set of variables
118 which might need PHI nodes (which can greatly improve compile-time 116 which might need PHI nodes (which can greatly improve compile-time
119 performance in some cases). 117 performance in some cases).
120 118
121 We also use the dominator walker to rewrite the function into SSA form 119 We also use the dominator walker to rewrite the function into SSA form
122 which reduces code duplication since the rewriting phase is inherently 120 which reduces code duplication since the rewriting phase is inherently
123 a walk of the dominator tree. 121 a walk of the dominator tree.
124 122
125 And (of course), we use the dominator walker to drive our dominator 123 And (of course), we use the dominator walker to drive our dominator
142 void 140 void
143 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) 141 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
144 { 142 {
145 void *bd = NULL; 143 void *bd = NULL;
146 basic_block dest; 144 basic_block dest;
147 gimple_stmt_iterator gsi;
148 bool is_interesting;
149 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); 145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
150 int sp = 0; 146 int sp = 0;
151 147
152 while (true) 148 while (true)
153 { 149 {
154 /* Don't worry about unreachable blocks. */ 150 /* Don't worry about unreachable blocks. */
155 if (EDGE_COUNT (bb->preds) > 0 151 if (EDGE_COUNT (bb->preds) > 0
156 || bb == ENTRY_BLOCK_PTR 152 || bb == ENTRY_BLOCK_PTR
157 || bb == EXIT_BLOCK_PTR) 153 || bb == EXIT_BLOCK_PTR)
158 { 154 {
159 /* If block BB is not interesting to the caller, then none of the
160 callbacks that walk the statements in BB are going to be
161 executed. */
162 is_interesting = walk_data->interesting_blocks == NULL
163 || TEST_BIT (walk_data->interesting_blocks,
164 bb->index);
165
166 /* Callback to initialize the local data structure. */ 155 /* Callback to initialize the local data structure. */
167 if (walk_data->initialize_block_local_data) 156 if (walk_data->initialize_block_local_data)
168 { 157 {
169 bool recycled; 158 bool recycled;
170 159
190 179
191 } 180 }
192 181
193 /* Callback for operations to execute before we have walked the 182 /* Callback for operations to execute before we have walked the
194 dominator children, but before we walk statements. */ 183 dominator children, but before we walk statements. */
195 if (walk_data->before_dom_children_before_stmts) 184 if (walk_data->before_dom_children)
196 (*walk_data->before_dom_children_before_stmts) (walk_data, bb); 185 (*walk_data->before_dom_children) (walk_data, bb);
197
198 /* Statement walk before walking dominator children. */
199 if (is_interesting && walk_data->before_dom_children_walk_stmts)
200 {
201 if (walk_data->walk_stmts_backward)
202 for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi);
203 gsi_prev (&gsi))
204 (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
205 gsi);
206 else
207 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
208 (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
209 gsi);
210 }
211
212 /* Callback for operations to execute before we have walked the
213 dominator children, and after we walk statements. */
214 if (walk_data->before_dom_children_after_stmts)
215 (*walk_data->before_dom_children_after_stmts) (walk_data, bb);
216 186
217 /* Mark the current BB to be popped out of the recursion stack 187 /* Mark the current BB to be popped out of the recursion stack
218 once children are processed. */ 188 once children are processed. */
219 worklist[sp++] = bb; 189 worklist[sp++] = bb;
220 worklist[sp++] = NULL; 190 worklist[sp++] = NULL;
221 191
222 for (dest = first_dom_son (walk_data->dom_direction, bb); 192 for (dest = first_dom_son (walk_data->dom_direction, bb);
223 dest; dest = next_dom_son (walk_data->dom_direction, dest)) 193 dest; dest = next_dom_son (walk_data->dom_direction, dest))
224 worklist[sp++] = dest; 194 worklist[sp++] = dest;
225 } 195 }
226 /* NULL is used to signalize pop operation in recursion stack. */ 196 /* NULL is used to mark pop operations in the recursion stack. */
227 while (sp > 0 && !worklist[sp - 1]) 197 while (sp > 0 && !worklist[sp - 1])
228 { 198 {
229 --sp; 199 --sp;
230 bb = worklist[--sp]; 200 bb = worklist[--sp];
231 is_interesting = walk_data->interesting_blocks == NULL 201
232 || TEST_BIT (walk_data->interesting_blocks,
233 bb->index);
234 /* Callback for operations to execute after we have walked the 202 /* Callback for operations to execute after we have walked the
235 dominator children, but before we walk statements. */ 203 dominator children, but before we walk statements. */
236 if (walk_data->after_dom_children_before_stmts) 204 if (walk_data->after_dom_children)
237 (*walk_data->after_dom_children_before_stmts) (walk_data, bb); 205 (*walk_data->after_dom_children) (walk_data, bb);
238
239 /* Statement walk after walking dominator children. */
240 if (is_interesting && walk_data->after_dom_children_walk_stmts)
241 {
242 if (walk_data->walk_stmts_backward)
243 for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi);
244 gsi_prev (&gsi))
245 (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
246 gsi);
247 else
248 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
249 (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
250 gsi);
251 }
252
253 /* Callback for operations to execute after we have walked the
254 dominator children and after we have walked statements. */
255 if (walk_data->after_dom_children_after_stmts)
256 (*walk_data->after_dom_children_after_stmts) (walk_data, bb);
257 206
258 if (walk_data->initialize_block_local_data) 207 if (walk_data->initialize_block_local_data)
259 { 208 {
260 /* And finally pop the record off the block local data stack. */ 209 /* And finally pop the record off the block local data stack. */
261 bd = VEC_pop (void_p, walk_data->block_data_stack); 210 bd = VEC_pop (void_p, walk_data->block_data_stack);