Mercurial > hg > CbC > CbC_gcc

comparison gcc/domwalk.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Generic dominator tree walker 1 /* Generic dominator tree walker
2 Copyright (C) 2003-2018 Free Software Foundation, Inc. 2 Copyright (C) 2003-2020 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com> 3 Contributed by Diego Novillo <dnovillo@redhat.com>
4 4
5 This file is part of GCC. 5 This file is part of GCC.
6 6
7 GCC is free software; you can redistribute it and/or modify 7 GCC is free software; you can redistribute it and/or modify
126 126
127 Walking statements is based on the block statement iterator abstraction, 127 Walking statements is based on the block statement iterator abstraction,
128 which is currently an abstraction over walking tree statements. Thus 128 which is currently an abstraction over walking tree statements. Thus
129 the dominator walker is currently only useful for trees. */ 129 the dominator walker is currently only useful for trees. */
130 130
131 /* Reverse postorder index of each basic block. */
132 static int *bb_postorder;
133
134 static int 131 static int
135 cmp_bb_postorder (const void *a, const void *b) 132 cmp_bb_postorder (const void *a, const void *b, void *data)
136 { 133 {
137 basic_block bb1 = *(const basic_block *)(a); 134 basic_block bb1 = *(const basic_block *)(a);
138 basic_block bb2 = *(const basic_block *)(b); 135 basic_block bb2 = *(const basic_block *)(b);
136 int *bb_postorder = (int *)data;
139 /* Place higher completion number first (pop off lower number first). */ 137 /* Place higher completion number first (pop off lower number first). */
140 return bb_postorder[bb2->index] - bb_postorder[bb1->index]; 138 return bb_postorder[bb2->index] - bb_postorder[bb1->index];
141 } 139 }
142 140
143 /* Permute array BBS of N basic blocks in postorder, 141 /* Permute array BBS of N basic blocks in postorder,
144 i.e. by descending number in BB_POSTORDER array. */ 142 i.e. by descending number in BB_POSTORDER array. */
145 143
146 static void 144 static void
147 sort_bbs_postorder (basic_block *bbs, int n) 145 sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
148 { 146 {
149 if (__builtin_expect (n == 2, true)) 147 if (__builtin_expect (n == 2, true))
150 { 148 {
151 basic_block bb0 = bbs[0], bb1 = bbs[1]; 149 basic_block bb0 = bbs[0], bb1 = bbs[1];
152 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) 150 if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
164 std::swap (bb0, bb1); 162 std::swap (bb0, bb1);
165 } 163 }
166 bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2; 164 bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
167 } 165 }
168 else 166 else
169 qsort (bbs, n, sizeof *bbs, cmp_bb_postorder); 167 gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
170 } 168 }
171 169
172 /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */ 170 /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
173 171
174 void 172 void
188 186
189 dom_walker::dom_walker (cdi_direction direction, 187 dom_walker::dom_walker (cdi_direction direction,
190 enum reachability reachability, 188 enum reachability reachability,
191 int *bb_index_to_rpo) 189 int *bb_index_to_rpo)
192 : m_dom_direction (direction), 190 : m_dom_direction (direction),
193 m_skip_unreachable_blocks (reachability != ALL_BLOCKS), 191 m_reachability (reachability),
194 m_user_bb_to_rpo (true), 192 m_user_bb_to_rpo (bb_index_to_rpo != NULL),
195 m_unreachable_dom (NULL), 193 m_unreachable_dom (NULL),
196 m_bb_to_rpo (bb_index_to_rpo) 194 m_bb_to_rpo (bb_index_to_rpo)
197 { 195 {
198 /* Set up edge flags if need be. */
199 switch (reachability)
200 {
201 default:
202 gcc_unreachable ();
203 case ALL_BLOCKS:
204 /* No need to touch edge flags. */
205 break;
206
207 case REACHABLE_BLOCKS:
208 set_all_edges_as_executable (cfun);
209 break;
210
211 case REACHABLE_BLOCKS_PRESERVING_FLAGS:
212 /* Preserve the edge flags. */
213 break;
214 }
215 }
216
217 /* Constructor for a dom walker. */
218
219 dom_walker::dom_walker (cdi_direction direction,
220 enum reachability reachability)
221 : m_dom_direction (direction),
222 m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
223 m_user_bb_to_rpo (false),
224 m_unreachable_dom (NULL),
225 m_bb_to_rpo (NULL)
226 {
227 /* Compute the basic-block index to RPO mapping. */
228 if (direction == CDI_DOMINATORS)
229 {
230 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
231 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
232 true);
233 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
234 for (int i = 0; i < postorder_num; ++i)
235 m_bb_to_rpo[postorder[i]] = i;
236 free (postorder);
237 }
238
239 /* Set up edge flags if need be. */
240 switch (reachability)
241 {
242 default:
243 gcc_unreachable ();
244 case ALL_BLOCKS:
245 /* No need to touch edge flags. */
246 break;
247
248 case REACHABLE_BLOCKS:
249 set_all_edges_as_executable (cfun);
250 break;
251
252 case REACHABLE_BLOCKS_PRESERVING_FLAGS:
253 /* Preserve the edge flags. */
254 break;
255 }
256 } 196 }
257 197
258 /* Destructor. */ 198 /* Destructor. */
259 199
260 dom_walker::~dom_walker () 200 dom_walker::~dom_walker ()
268 bool 208 bool
269 dom_walker::bb_reachable (struct function *fun, basic_block bb) 209 dom_walker::bb_reachable (struct function *fun, basic_block bb)
270 { 210 {
271 /* If we're not skipping unreachable blocks, then assume everything 211 /* If we're not skipping unreachable blocks, then assume everything
272 is reachable. */ 212 is reachable. */
273 if (!m_skip_unreachable_blocks) 213 if (m_reachability == ALL_BLOCKS)
274 return true; 214 return true;
275 215
276 /* If any of the predecessor edges that do not come from blocks dominated 216 /* If any of the predecessor edges that do not come from blocks dominated
277 by us are still marked as possibly executable consider this block 217 by us are still marked as possibly executable consider this block
278 reachable. */ 218 reachable. */
329 BB is the basic block we are currently visiting. */ 269 BB is the basic block we are currently visiting. */
330 270
331 void 271 void
332 dom_walker::walk (basic_block bb) 272 dom_walker::walk (basic_block bb)
333 { 273 {
274 /* Compute the basic-block index to RPO mapping lazily. */
275 if (!m_bb_to_rpo
276 && m_dom_direction == CDI_DOMINATORS)
277 {
278 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
279 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
280 true);
281 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
282 for (int i = 0; i < postorder_num; ++i)
283 m_bb_to_rpo[postorder[i]] = i;
284 free (postorder);
285 }
286
287 /* Set up edge flags if need be. */
288 if (m_reachability == REACHABLE_BLOCKS)
289 set_all_edges_as_executable (cfun);
290
334 basic_block dest; 291 basic_block dest;
335 basic_block *worklist = XNEWVEC (basic_block, 292 basic_block *worklist = XNEWVEC (basic_block,
336 n_basic_blocks_for_fn (cfun) * 2); 293 n_basic_blocks_for_fn (cfun) * 2);
337 int sp = 0; 294 int sp = 0;
338 bb_postorder = m_bb_to_rpo;
339 295
340 while (true) 296 while (true)
341 { 297 {
342 /* Don't worry about unreachable blocks. */ 298 /* Don't worry about unreachable blocks. */
343 if (EDGE_COUNT (bb->preds) > 0 299 if (EDGE_COUNT (bb->preds) > 0
378 worklist[sp++] = dest; 334 worklist[sp++] = dest;
379 /* Sort worklist after RPO order if requested. */ 335 /* Sort worklist after RPO order if requested. */
380 if (sp - saved_sp > 1 336 if (sp - saved_sp > 1
381 && m_dom_direction == CDI_DOMINATORS 337 && m_dom_direction == CDI_DOMINATORS
382 && m_bb_to_rpo) 338 && m_bb_to_rpo)
383 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); 339 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp,
340 m_bb_to_rpo);
384 } 341 }
385 } 342 }
386 /* NULL is used to mark pop operations in the recursion stack. */ 343 /* NULL is used to mark pop operations in the recursion stack. */
387 while (sp > 0 && !worklist[sp - 1]) 344 while (sp > 0 && !worklist[sp - 1])
388 { 345 {
399 if (sp) 356 if (sp)
400 bb = worklist[--sp]; 357 bb = worklist[--sp];
401 else 358 else
402 break; 359 break;
403 } 360 }
404 bb_postorder = NULL;
405 free (worklist); 361 free (worklist);
406 } 362 }