View | Details | Raw Unified | Return to bug 56113 | Differences between
and this patch

Collapse All | Expand All

(-)gcc/domwalk.c (-39 / +43 lines)
Lines 128-133 along with GCC; see the file COPYING3. Link Here
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
static int *bb_postorder;
132
133
static int
134
cmp_bb_postorder (const void *a, const void *b)
135
{
136
  basic_block bb1 = *(basic_block *)a;
137
  basic_block bb2 = *(basic_block *)b;
138
  if (bb1->index == bb2->index)
139
    return 0;
140
  /* Place higher completion number first (pop off lower number first).  */
141
  if (bb_postorder[bb1->index] > bb_postorder[bb2->index])
142
    return -1;
143
  return 1;
144
}
145
131
/* Recursively walk the dominator tree.
146
/* Recursively walk the dominator tree.
132
147
133
   WALK_DATA contains a set of callbacks to perform pass-specific
148
   WALK_DATA contains a set of callbacks to perform pass-specific
Lines 143-151 walk_dominator_tree (struct dom_walk_dat Link Here
143
  basic_block dest;
158
  basic_block dest;
144
  basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
159
  basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
145
  int sp = 0;
160
  int sp = 0;
146
  sbitmap visited = sbitmap_alloc (last_basic_block + 1);
161
  int *postorder, postorder_num;
147
  bitmap_clear (visited);
162
148
  bitmap_set_bit (visited, ENTRY_BLOCK_PTR->index);
163
  if (walk_data->dom_direction == CDI_DOMINATORS)
164
    {
165
      postorder = XNEWVEC (int, n_basic_blocks);
166
      postorder_num = inverted_post_order_compute (postorder);
167
      bb_postorder = XNEWVEC (int, last_basic_block);
168
      for (int i = 0; i < postorder_num; ++i)
169
	bb_postorder[postorder[i]] = i;
170
      free (postorder);
171
    }
149
172
150
  while (true)
173
  while (true)
151
    {
174
    {
Lines 186-201 walk_dominator_tree (struct dom_walk_dat Link Here
186
	  if (walk_data->before_dom_children)
209
	  if (walk_data->before_dom_children)
187
	    (*walk_data->before_dom_children) (walk_data, bb);
210
	    (*walk_data->before_dom_children) (walk_data, bb);
188
211
189
	  bitmap_set_bit (visited, bb->index);
190
191
	  /* Mark the current BB to be popped out of the recursion stack
212
	  /* Mark the current BB to be popped out of the recursion stack
192
	     once children are processed.  */
213
	     once children are processed.  */
193
	  worklist[sp++] = bb;
214
	  worklist[sp++] = bb;
194
	  worklist[sp++] = NULL;
215
	  worklist[sp++] = NULL;
195
216
217
	  int saved_sp = sp;
196
	  for (dest = first_dom_son (walk_data->dom_direction, bb);
218
	  for (dest = first_dom_son (walk_data->dom_direction, bb);
197
	       dest; dest = next_dom_son (walk_data->dom_direction, dest))
219
	       dest; dest = next_dom_son (walk_data->dom_direction, dest))
198
	    worklist[sp++] = dest;
220
	    worklist[sp++] = dest;
221
	  if (walk_data->dom_direction == CDI_DOMINATORS)
222
	    switch (sp - saved_sp)
223
	      {
224
	      case 0:
225
	      case 1:
226
		break;
227
	      default:
228
		qsort (&worklist[saved_sp], sp - saved_sp,
229
		       sizeof (basic_block), cmp_bb_postorder);
230
	      }
199
	}
231
	}
200
      /* NULL is used to mark pop operations in the recursion stack.  */
232
      /* NULL is used to mark pop operations in the recursion stack.  */
201
      while (sp > 0 && !worklist[sp - 1])
233
      while (sp > 0 && !worklist[sp - 1])
Lines 217-260 walk_dominator_tree (struct dom_walk_dat Link Here
217
	    }
249
	    }
218
	}
250
	}
219
      if (sp)
251
      if (sp)
220
	{
252
	bb = worklist[--sp];
221
	  int spp;
222
	  spp = sp - 1;
223
	  if (walk_data->dom_direction == CDI_DOMINATORS)
224
	    /* Find the dominator son that has all its predecessors
225
	       visited and continue with that.  */
226
	    while (1)
227
	      {
228
		edge_iterator ei;
229
		edge e;
230
		bool found = true;
231
		bb = worklist[spp];
232
		FOR_EACH_EDGE (e, ei, bb->preds)
233
		  {
234
		    if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
235
			&& !bitmap_bit_p (visited, e->src->index))
236
		      {
237
			found = false;
238
			break;
239
		      }
240
		  }
241
		if (found)
242
		  break;
243
		/* If we didn't find a dom child with all visited
244
		   predecessors just use the candidate we were checking.
245
		   This happens for candidates in irreducible loops.  */
246
		if (!worklist[spp - 1])
247
		  break;
248
		--spp;
249
	      }
250
	  bb = worklist[spp];
251
	  worklist[spp] = worklist[--sp];
252
	}
253
      else
253
      else
254
	break;
254
	break;
255
    }
255
    }
256
  if (walk_data->dom_direction == CDI_DOMINATORS)
257
    {
258
      free (bb_postorder);
259
      bb_postorder = NULL;
260
    }
256
  free (worklist);
261
  free (worklist);
257
  sbitmap_free (visited);
258
}
262
}
259
263
260
void
264
void

Return to bug 56113