Mercurial > hg > CbC > CbC_gcc

comparison gcc/domwalk.c @ 63:b7f97abdc517 gcc-4.6-20100522

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.5.0 to gcc-4.6
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Mon, 24 May 2010 12:47:05 +0900
parents 77e2b8dfacca
children f6334be47118
comparison
equal deleted inserted replaced
56:3c8a44c06a95 63:b7f97abdc517
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 "basic-block.h" 26 #include "basic-block.h"
27 #include "domwalk.h" 27 #include "domwalk.h"
28 #include "ggc.h" 28 #include "sbitmap.h"
29 29
30 /* This file implements a generic walker for dominator trees. 30 /* This file implements a generic walker for dominator trees.
31 31
32 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,
33 immediate dominators and the dominator tree. 33 immediate dominators and the dominator tree.
142 { 142 {
143 void *bd = NULL; 143 void *bd = NULL;
144 basic_block dest; 144 basic_block dest;
145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); 145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
146 int sp = 0; 146 int sp = 0;
147 sbitmap visited = sbitmap_alloc (last_basic_block + 1);
148 sbitmap_zero (visited);
149 SET_BIT (visited, ENTRY_BLOCK_PTR->index);
147 150
148 while (true) 151 while (true)
149 { 152 {
150 /* Don't worry about unreachable blocks. */ 153 /* Don't worry about unreachable blocks. */
151 if (EDGE_COUNT (bb->preds) > 0 154 if (EDGE_COUNT (bb->preds) > 0
182 /* Callback for operations to execute before we have walked the 185 /* Callback for operations to execute before we have walked the
183 dominator children, but before we walk statements. */ 186 dominator children, but before we walk statements. */
184 if (walk_data->before_dom_children) 187 if (walk_data->before_dom_children)
185 (*walk_data->before_dom_children) (walk_data, bb); 188 (*walk_data->before_dom_children) (walk_data, bb);
186 189
190 SET_BIT (visited, bb->index);
191
187 /* Mark the current BB to be popped out of the recursion stack 192 /* Mark the current BB to be popped out of the recursion stack
188 once children are processed. */ 193 once children are processed. */
189 worklist[sp++] = bb; 194 worklist[sp++] = bb;
190 worklist[sp++] = NULL; 195 worklist[sp++] = NULL;
191 196
211 /* And save the block data so that we can re-use it. */ 216 /* 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); 217 VEC_safe_push (void_p, heap, walk_data->free_block_data, bd);
213 } 218 }
214 } 219 }
215 if (sp) 220 if (sp)
216 bb = worklist[--sp]; 221 {
222 int spp;
223 spp = sp - 1;
224 if (walk_data->dom_direction == CDI_DOMINATORS)
225 /* Find the dominator son that has all its predecessors
226 visited and continue with that. */
227 while (1)
228 {
229 edge_iterator ei;
230 edge e;
231 bool found = true;
232 bb = worklist[spp];
233 FOR_EACH_EDGE (e, ei, bb->preds)
234 {
235 if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
236 && !TEST_BIT (visited, e->src->index))
237 {
238 found = false;
239 break;
240 }
241 }
242 if (found)
243 break;
244 /* If we didn't find a dom child with all visited
245 predecessors just use the candidate we were checking.
246 This happens for candidates in irreducible loops. */
247 if (!worklist[spp - 1])
248 break;
249 --spp;
250 }
251 bb = worklist[spp];
252 worklist[spp] = worklist[--sp];
253 }
217 else 254 else
218 break; 255 break;
219 } 256 }
220 free (worklist); 257 free (worklist);
258 sbitmap_free (visited);
221 } 259 }
222 260
223 void 261 void
224 init_walk_dominator_tree (struct dom_walk_data *walk_data) 262 init_walk_dominator_tree (struct dom_walk_data *walk_data)
225 { 263 {