OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [dominance.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Calculate (post)dominators in slightly super-linear time.
2
   Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Michael Matz (matz@ifh.de).
5
 
6
   This file is part of GCC.
7
 
8
   GCC is free software; you can redistribute it and/or modify it
9
   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, but WITHOUT
14
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15
   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
16
   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
/* This file implements the well known algorithm from Lengauer and Tarjan
23
   to compute the dominators in a control flow graph.  A basic block D is said
24
   to dominate another block X, when all paths from the entry node of the CFG
25
   to X go also over D.  The dominance relation is a transitive reflexive
26
   relation and its minimal transitive reduction is a tree, called the
27
   dominator tree.  So for each block X besides the entry block exists a
28
   block I(X), called the immediate dominator of X, which is the parent of X
29
   in the dominator tree.
30
 
31
   The algorithm computes this dominator tree implicitly by computing for
32
   each block its immediate dominator.  We use tree balancing and path
33
   compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
34
   slowly growing functional inverse of the Ackerman function.  */
35
 
36
#include "config.h"
37
#include "system.h"
38
#include "coretypes.h"
39
#include "tm.h"
40
#include "rtl.h"
41
#include "hard-reg-set.h"
42
#include "obstack.h"
43
#include "basic-block.h"
44
#include "toplev.h"
45
#include "et-forest.h"
46
#include "timevar.h"
47
#include "vecprim.h"
48
#include "pointer-set.h"
49
#include "graphds.h"
50
 
51
/* We name our nodes with integers, beginning with 1.  Zero is reserved for
52
   'undefined' or 'end of list'.  The name of each node is given by the dfs
53
   number of the corresponding basic block.  Please note, that we include the
54
   artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
55
   support multiple entry points.  Its dfs number is of course 1.  */
56
 
57
/* Type of Basic Block aka. TBB */
58
typedef unsigned int TBB;
59
 
60
/* We work in a poor-mans object oriented fashion, and carry an instance of
61
   this structure through all our 'methods'.  It holds various arrays
62
   reflecting the (sub)structure of the flowgraph.  Most of them are of type
63
   TBB and are also indexed by TBB.  */
64
 
65
struct dom_info
66
{
67
  /* The parent of a node in the DFS tree.  */
68
  TBB *dfs_parent;
69
  /* For a node x key[x] is roughly the node nearest to the root from which
70
     exists a way to x only over nodes behind x.  Such a node is also called
71
     semidominator.  */
72
  TBB *key;
73
  /* The value in path_min[x] is the node y on the path from x to the root of
74
     the tree x is in with the smallest key[y].  */
75
  TBB *path_min;
76
  /* bucket[x] points to the first node of the set of nodes having x as key.  */
77
  TBB *bucket;
78
  /* And next_bucket[x] points to the next node.  */
79
  TBB *next_bucket;
80
  /* After the algorithm is done, dom[x] contains the immediate dominator
81
     of x.  */
82
  TBB *dom;
83
 
84
  /* The following few fields implement the structures needed for disjoint
85
     sets.  */
86
  /* set_chain[x] is the next node on the path from x to the representative
87
     of the set containing x.  If set_chain[x]==0 then x is a root.  */
88
  TBB *set_chain;
89
  /* set_size[x] is the number of elements in the set named by x.  */
90
  unsigned int *set_size;
91
  /* set_child[x] is used for balancing the tree representing a set.  It can
92
     be understood as the next sibling of x.  */
93
  TBB *set_child;
94
 
95
  /* If b is the number of a basic block (BB->index), dfs_order[b] is the
96
     number of that node in DFS order counted from 1.  This is an index
97
     into most of the other arrays in this structure.  */
98
  TBB *dfs_order;
99
  /* If x is the DFS-index of a node which corresponds with a basic block,
100
     dfs_to_bb[x] is that basic block.  Note, that in our structure there are
101
     more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
102
     is true for every basic block bb, but not the opposite.  */
103
  basic_block *dfs_to_bb;
104
 
105
  /* This is the next free DFS number when creating the DFS tree.  */
106
  unsigned int dfsnum;
107
  /* The number of nodes in the DFS tree (==dfsnum-1).  */
108
  unsigned int nodes;
109
 
110
  /* Blocks with bits set here have a fake edge to EXIT.  These are used
111
     to turn a DFS forest into a proper tree.  */
112
  bitmap fake_exit_edge;
113
};
114
 
115
static void init_dom_info (struct dom_info *, enum cdi_direction);
116
static void free_dom_info (struct dom_info *);
117
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
118
static void calc_dfs_tree (struct dom_info *, bool);
119
static void compress (struct dom_info *, TBB);
120
static TBB eval (struct dom_info *, TBB);
121
static void link_roots (struct dom_info *, TBB, TBB);
122
static void calc_idoms (struct dom_info *, bool);
123
void debug_dominance_info (enum cdi_direction);
124
void debug_dominance_tree (enum cdi_direction, basic_block);
125
 
126
/* Helper macro for allocating and initializing an array,
127
   for aesthetic reasons.  */
128
#define init_ar(var, type, num, content)                        \
129
  do                                                            \
130
    {                                                           \
131
      unsigned int i = 1;    /* Catch content == i.  */         \
132
      if (! (content))                                          \
133
        (var) = XCNEWVEC (type, num);                           \
134
      else                                                      \
135
        {                                                       \
136
          (var) = XNEWVEC (type, (num));                        \
137
          for (i = 0; i < num; i++)                              \
138
            (var)[i] = (content);                               \
139
        }                                                       \
140
    }                                                           \
141
  while (0)
142
 
143
/* Allocate all needed memory in a pessimistic fashion (so we round up).
144
   This initializes the contents of DI, which already must be allocated.  */
145
 
146
static void
147
init_dom_info (struct dom_info *di, enum cdi_direction dir)
148
{
149
  /* We need memory for n_basic_blocks nodes.  */
150
  unsigned int num = n_basic_blocks;
151
  init_ar (di->dfs_parent, TBB, num, 0);
152
  init_ar (di->path_min, TBB, num, i);
153
  init_ar (di->key, TBB, num, i);
154
  init_ar (di->dom, TBB, num, 0);
155
 
156
  init_ar (di->bucket, TBB, num, 0);
157
  init_ar (di->next_bucket, TBB, num, 0);
158
 
159
  init_ar (di->set_chain, TBB, num, 0);
160
  init_ar (di->set_size, unsigned int, num, 1);
161
  init_ar (di->set_child, TBB, num, 0);
162
 
163
  init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
164
  init_ar (di->dfs_to_bb, basic_block, num, 0);
165
 
166
  di->dfsnum = 1;
167
  di->nodes = 0;
168
 
169
  switch (dir)
170
    {
171
      case CDI_DOMINATORS:
172
        di->fake_exit_edge = NULL;
173
        break;
174
      case CDI_POST_DOMINATORS:
175
        di->fake_exit_edge = BITMAP_ALLOC (NULL);
176
        break;
177
      default:
178
        gcc_unreachable ();
179
        break;
180
    }
181
}
182
 
183
#undef init_ar
184
 
185
/* Map dominance calculation type to array index used for various
186
   dominance information arrays.  This version is simple -- it will need
187
   to be modified, obviously, if additional values are added to
188
   cdi_direction.  */
189
 
190
static unsigned int
191
dom_convert_dir_to_idx (enum cdi_direction dir)
192
{
193
  gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
194
  return dir - 1;
195
}
196
 
197
/* Free all allocated memory in DI, but not DI itself.  */
198
 
199
static void
200
free_dom_info (struct dom_info *di)
201
{
202
  free (di->dfs_parent);
203
  free (di->path_min);
204
  free (di->key);
205
  free (di->dom);
206
  free (di->bucket);
207
  free (di->next_bucket);
208
  free (di->set_chain);
209
  free (di->set_size);
210
  free (di->set_child);
211
  free (di->dfs_order);
212
  free (di->dfs_to_bb);
213
  BITMAP_FREE (di->fake_exit_edge);
214
}
215
 
216
/* The nonrecursive variant of creating a DFS tree.  DI is our working
217
   structure, BB the starting basic block for this tree and REVERSE
218
   is true, if predecessors should be visited instead of successors of a
219
   node.  After this is done all nodes reachable from BB were visited, have
220
   assigned their dfs number and are linked together to form a tree.  */
221
 
222
static void
223
calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
224
{
225
  /* We call this _only_ if bb is not already visited.  */
226
  edge e;
227
  TBB child_i, my_i = 0;
228
  edge_iterator *stack;
229
  edge_iterator ei, einext;
230
  int sp;
231
  /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
232
     problem).  */
233
  basic_block en_block;
234
  /* Ending block.  */
235
  basic_block ex_block;
236
 
237
  stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
238
  sp = 0;
239
 
240
  /* Initialize our border blocks, and the first edge.  */
241
  if (reverse)
242
    {
243
      ei = ei_start (bb->preds);
244
      en_block = EXIT_BLOCK_PTR;
245
      ex_block = ENTRY_BLOCK_PTR;
246
    }
247
  else
248
    {
249
      ei = ei_start (bb->succs);
250
      en_block = ENTRY_BLOCK_PTR;
251
      ex_block = EXIT_BLOCK_PTR;
252
    }
253
 
254
  /* When the stack is empty we break out of this loop.  */
255
  while (1)
256
    {
257
      basic_block bn;
258
 
259
      /* This loop traverses edges e in depth first manner, and fills the
260
         stack.  */
261
      while (!ei_end_p (ei))
262
        {
263
          e = ei_edge (ei);
264
 
265
          /* Deduce from E the current and the next block (BB and BN), and the
266
             next edge.  */
267
          if (reverse)
268
            {
269
              bn = e->src;
270
 
271
              /* If the next node BN is either already visited or a border
272
                 block the current edge is useless, and simply overwritten
273
                 with the next edge out of the current node.  */
274
              if (bn == ex_block || di->dfs_order[bn->index])
275
                {
276
                  ei_next (&ei);
277
                  continue;
278
                }
279
              bb = e->dest;
280
              einext = ei_start (bn->preds);
281
            }
282
          else
283
            {
284
              bn = e->dest;
285
              if (bn == ex_block || di->dfs_order[bn->index])
286
                {
287
                  ei_next (&ei);
288
                  continue;
289
                }
290
              bb = e->src;
291
              einext = ei_start (bn->succs);
292
            }
293
 
294
          gcc_assert (bn != en_block);
295
 
296
          /* Fill the DFS tree info calculatable _before_ recursing.  */
297
          if (bb != en_block)
298
            my_i = di->dfs_order[bb->index];
299
          else
300
            my_i = di->dfs_order[last_basic_block];
301
          child_i = di->dfs_order[bn->index] = di->dfsnum++;
302
          di->dfs_to_bb[child_i] = bn;
303
          di->dfs_parent[child_i] = my_i;
304
 
305
          /* Save the current point in the CFG on the stack, and recurse.  */
306
          stack[sp++] = ei;
307
          ei = einext;
308
        }
309
 
310
      if (!sp)
311
        break;
312
      ei = stack[--sp];
313
 
314
      /* OK.  The edge-list was exhausted, meaning normally we would
315
         end the recursion.  After returning from the recursive call,
316
         there were (may be) other statements which were run after a
317
         child node was completely considered by DFS.  Here is the
318
         point to do it in the non-recursive variant.
319
         E.g. The block just completed is in e->dest for forward DFS,
320
         the block not yet completed (the parent of the one above)
321
         in e->src.  This could be used e.g. for computing the number of
322
         descendants or the tree depth.  */
323
      ei_next (&ei);
324
    }
325
  free (stack);
326
}
327
 
328
/* The main entry for calculating the DFS tree or forest.  DI is our working
329
   structure and REVERSE is true, if we are interested in the reverse flow
330
   graph.  In that case the result is not necessarily a tree but a forest,
331
   because there may be nodes from which the EXIT_BLOCK is unreachable.  */
332
 
333
static void
334
calc_dfs_tree (struct dom_info *di, bool reverse)
335
{
336
  /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
337
  basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
338
  di->dfs_order[last_basic_block] = di->dfsnum;
339
  di->dfs_to_bb[di->dfsnum] = begin;
340
  di->dfsnum++;
341
 
342
  calc_dfs_tree_nonrec (di, begin, reverse);
343
 
344
  if (reverse)
345
    {
346
      /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
347
         They are reverse-unreachable.  In the dom-case we disallow such
348
         nodes, but in post-dom we have to deal with them.
349
 
350
         There are two situations in which this occurs.  First, noreturn
351
         functions.  Second, infinite loops.  In the first case we need to
352
         pretend that there is an edge to the exit block.  In the second
353
         case, we wind up with a forest.  We need to process all noreturn
354
         blocks before we know if we've got any infinite loops.  */
355
 
356
      basic_block b;
357
      bool saw_unconnected = false;
358
 
359
      FOR_EACH_BB_REVERSE (b)
360
        {
361
          if (EDGE_COUNT (b->succs) > 0)
362
            {
363
              if (di->dfs_order[b->index] == 0)
364
                saw_unconnected = true;
365
              continue;
366
            }
367
          bitmap_set_bit (di->fake_exit_edge, b->index);
368
          di->dfs_order[b->index] = di->dfsnum;
369
          di->dfs_to_bb[di->dfsnum] = b;
370
          di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
371
          di->dfsnum++;
372
          calc_dfs_tree_nonrec (di, b, reverse);
373
        }
374
 
375
      if (saw_unconnected)
376
        {
377
          FOR_EACH_BB_REVERSE (b)
378
            {
379
              if (di->dfs_order[b->index])
380
                continue;
381
              bitmap_set_bit (di->fake_exit_edge, b->index);
382
              di->dfs_order[b->index] = di->dfsnum;
383
              di->dfs_to_bb[di->dfsnum] = b;
384
              di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
385
              di->dfsnum++;
386
              calc_dfs_tree_nonrec (di, b, reverse);
387
            }
388
        }
389
    }
390
 
391
  di->nodes = di->dfsnum - 1;
392
 
393
  /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
394
  gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
395
}
396
 
397
/* Compress the path from V to the root of its set and update path_min at the
398
   same time.  After compress(di, V) set_chain[V] is the root of the set V is
399
   in and path_min[V] is the node with the smallest key[] value on the path
400
   from V to that root.  */
401
 
402
static void
403
compress (struct dom_info *di, TBB v)
404
{
405
  /* Btw. It's not worth to unrecurse compress() as the depth is usually not
406
     greater than 5 even for huge graphs (I've not seen call depth > 4).
407
     Also performance wise compress() ranges _far_ behind eval().  */
408
  TBB parent = di->set_chain[v];
409
  if (di->set_chain[parent])
410
    {
411
      compress (di, parent);
412
      if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
413
        di->path_min[v] = di->path_min[parent];
414
      di->set_chain[v] = di->set_chain[parent];
415
    }
416
}
417
 
418
/* Compress the path from V to the set root of V if needed (when the root has
419
   changed since the last call).  Returns the node with the smallest key[]
420
   value on the path from V to the root.  */
421
 
422
static inline TBB
423
eval (struct dom_info *di, TBB v)
424
{
425
  /* The representative of the set V is in, also called root (as the set
426
     representation is a tree).  */
427
  TBB rep = di->set_chain[v];
428
 
429
  /* V itself is the root.  */
430
  if (!rep)
431
    return di->path_min[v];
432
 
433
  /* Compress only if necessary.  */
434
  if (di->set_chain[rep])
435
    {
436
      compress (di, v);
437
      rep = di->set_chain[v];
438
    }
439
 
440
  if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
441
    return di->path_min[v];
442
  else
443
    return di->path_min[rep];
444
}
445
 
446
/* This essentially merges the two sets of V and W, giving a single set with
447
   the new root V.  The internal representation of these disjoint sets is a
448
   balanced tree.  Currently link(V,W) is only used with V being the parent
449
   of W.  */
450
 
451
static void
452
link_roots (struct dom_info *di, TBB v, TBB w)
453
{
454
  TBB s = w;
455
 
456
  /* Rebalance the tree.  */
457
  while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
458
    {
459
      if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
460
          >= 2 * di->set_size[di->set_child[s]])
461
        {
462
          di->set_chain[di->set_child[s]] = s;
463
          di->set_child[s] = di->set_child[di->set_child[s]];
464
        }
465
      else
466
        {
467
          di->set_size[di->set_child[s]] = di->set_size[s];
468
          s = di->set_chain[s] = di->set_child[s];
469
        }
470
    }
471
 
472
  di->path_min[s] = di->path_min[w];
473
  di->set_size[v] += di->set_size[w];
474
  if (di->set_size[v] < 2 * di->set_size[w])
475
    {
476
      TBB tmp = s;
477
      s = di->set_child[v];
478
      di->set_child[v] = tmp;
479
    }
480
 
481
  /* Merge all subtrees.  */
482
  while (s)
483
    {
484
      di->set_chain[s] = v;
485
      s = di->set_child[s];
486
    }
487
}
488
 
489
/* This calculates the immediate dominators (or post-dominators if REVERSE is
490
   true).  DI is our working structure and should hold the DFS forest.
491
   On return the immediate dominator to node V is in di->dom[V].  */
492
 
493
static void
494
calc_idoms (struct dom_info *di, bool reverse)
495
{
496
  TBB v, w, k, par;
497
  basic_block en_block;
498
  edge_iterator ei, einext;
499
 
500
  if (reverse)
501
    en_block = EXIT_BLOCK_PTR;
502
  else
503
    en_block = ENTRY_BLOCK_PTR;
504
 
505
  /* Go backwards in DFS order, to first look at the leafs.  */
506
  v = di->nodes;
507
  while (v > 1)
508
    {
509
      basic_block bb = di->dfs_to_bb[v];
510
      edge e;
511
 
512
      par = di->dfs_parent[v];
513
      k = v;
514
 
515
      ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
516
 
517
      if (reverse)
518
        {
519
          /* If this block has a fake edge to exit, process that first.  */
520
          if (bitmap_bit_p (di->fake_exit_edge, bb->index))
521
            {
522
              einext = ei;
523
              einext.index = 0;
524
              goto do_fake_exit_edge;
525
            }
526
        }
527
 
528
      /* Search all direct predecessors for the smallest node with a path
529
         to them.  That way we have the smallest node with also a path to
530
         us only over nodes behind us.  In effect we search for our
531
         semidominator.  */
532
      while (!ei_end_p (ei))
533
        {
534
          TBB k1;
535
          basic_block b;
536
 
537
          e = ei_edge (ei);
538
          b = (reverse) ? e->dest : e->src;
539
          einext = ei;
540
          ei_next (&einext);
541
 
542
          if (b == en_block)
543
            {
544
            do_fake_exit_edge:
545
              k1 = di->dfs_order[last_basic_block];
546
            }
547
          else
548
            k1 = di->dfs_order[b->index];
549
 
550
          /* Call eval() only if really needed.  If k1 is above V in DFS tree,
551
             then we know, that eval(k1) == k1 and key[k1] == k1.  */
552
          if (k1 > v)
553
            k1 = di->key[eval (di, k1)];
554
          if (k1 < k)
555
            k = k1;
556
 
557
          ei = einext;
558
        }
559
 
560
      di->key[v] = k;
561
      link_roots (di, par, v);
562
      di->next_bucket[v] = di->bucket[k];
563
      di->bucket[k] = v;
564
 
565
      /* Transform semidominators into dominators.  */
566
      for (w = di->bucket[par]; w; w = di->next_bucket[w])
567
        {
568
          k = eval (di, w);
569
          if (di->key[k] < di->key[w])
570
            di->dom[w] = k;
571
          else
572
            di->dom[w] = par;
573
        }
574
      /* We don't need to cleanup next_bucket[].  */
575
      di->bucket[par] = 0;
576
      v--;
577
    }
578
 
579
  /* Explicitly define the dominators.  */
580
  di->dom[1] = 0;
581
  for (v = 2; v <= di->nodes; v++)
582
    if (di->dom[v] != di->key[v])
583
      di->dom[v] = di->dom[di->dom[v]];
584
}
585
 
586
/* Assign dfs numbers starting from NUM to NODE and its sons.  */
587
 
588
static void
589
assign_dfs_numbers (struct et_node *node, int *num)
590
{
591
  struct et_node *son;
592
 
593
  node->dfs_num_in = (*num)++;
594
 
595
  if (node->son)
596
    {
597
      assign_dfs_numbers (node->son, num);
598
      for (son = node->son->right; son != node->son; son = son->right)
599
        assign_dfs_numbers (son, num);
600
    }
601
 
602
  node->dfs_num_out = (*num)++;
603
}
604
 
605
/* Compute the data necessary for fast resolving of dominator queries in a
606
   static dominator tree.  */
607
 
608
static void
609
compute_dom_fast_query (enum cdi_direction dir)
610
{
611
  int num = 0;
612
  basic_block bb;
613
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
614
 
615
  gcc_assert (dom_info_available_p (dir));
616
 
617
  if (dom_computed[dir_index] == DOM_OK)
618
    return;
619
 
620
  FOR_ALL_BB (bb)
621
    {
622
      if (!bb->dom[dir_index]->father)
623
        assign_dfs_numbers (bb->dom[dir_index], &num);
624
    }
625
 
626
  dom_computed[dir_index] = DOM_OK;
627
}
628
 
629
/* The main entry point into this module.  DIR is set depending on whether
630
   we want to compute dominators or postdominators.  */
631
 
632
void
633
calculate_dominance_info (enum cdi_direction dir)
634
{
635
  struct dom_info di;
636
  basic_block b;
637
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
638
  bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
639
 
640
  if (dom_computed[dir_index] == DOM_OK)
641
    return;
642
 
643
  timevar_push (TV_DOMINANCE);
644
  if (!dom_info_available_p (dir))
645
    {
646
      gcc_assert (!n_bbs_in_dom_tree[dir_index]);
647
 
648
      FOR_ALL_BB (b)
649
        {
650
          b->dom[dir_index] = et_new_tree (b);
651
        }
652
      n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
653
 
654
      init_dom_info (&di, dir);
655
      calc_dfs_tree (&di, reverse);
656
      calc_idoms (&di, reverse);
657
 
658
      FOR_EACH_BB (b)
659
        {
660
          TBB d = di.dom[di.dfs_order[b->index]];
661
 
662
          if (di.dfs_to_bb[d])
663
            et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
664
        }
665
 
666
      free_dom_info (&di);
667
      dom_computed[dir_index] = DOM_NO_FAST_QUERY;
668
    }
669
 
670
  compute_dom_fast_query (dir);
671
 
672
  timevar_pop (TV_DOMINANCE);
673
}
674
 
675
/* Free dominance information for direction DIR.  */
676
void
677
free_dominance_info (enum cdi_direction dir)
678
{
679
  basic_block bb;
680
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
681
 
682
  if (!dom_info_available_p (dir))
683
    return;
684
 
685
  FOR_ALL_BB (bb)
686
    {
687
      et_free_tree_force (bb->dom[dir_index]);
688
      bb->dom[dir_index] = NULL;
689
    }
690
  et_free_pools ();
691
 
692
  n_bbs_in_dom_tree[dir_index] = 0;
693
 
694
  dom_computed[dir_index] = DOM_NONE;
695
}
696
 
697
/* Return the immediate dominator of basic block BB.  */
698
basic_block
699
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
700
{
701
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
702
  struct et_node *node = bb->dom[dir_index];
703
 
704
  gcc_assert (dom_computed[dir_index]);
705
 
706
  if (!node->father)
707
    return NULL;
708
 
709
  return (basic_block) node->father->data;
710
}
711
 
712
/* Set the immediate dominator of the block possibly removing
713
   existing edge.  NULL can be used to remove any edge.  */
714
void
715
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
716
                         basic_block dominated_by)
717
{
718
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
719
  struct et_node *node = bb->dom[dir_index];
720
 
721
  gcc_assert (dom_computed[dir_index]);
722
 
723
  if (node->father)
724
    {
725
      if (node->father->data == dominated_by)
726
        return;
727
      et_split (node);
728
    }
729
 
730
  if (dominated_by)
731
    et_set_father (node, dominated_by->dom[dir_index]);
732
 
733
  if (dom_computed[dir_index] == DOM_OK)
734
    dom_computed[dir_index] = DOM_NO_FAST_QUERY;
735
}
736
 
737
/* Returns the list of basic blocks immediately dominated by BB, in the
738
   direction DIR.  */
739
VEC (basic_block, heap) *
740
get_dominated_by (enum cdi_direction dir, basic_block bb)
741
{
742
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
743
  struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
744
  VEC (basic_block, heap) *bbs = NULL;
745
 
746
  gcc_assert (dom_computed[dir_index]);
747
 
748
  if (!son)
749
    return NULL;
750
 
751
  VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
752
  for (ason = son->right; ason != son; ason = ason->right)
753
    VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
754
 
755
  return bbs;
756
}
757
 
758
/* Returns the list of basic blocks that are immediately dominated (in
759
   direction DIR) by some block between N_REGION ones stored in REGION,
760
   except for blocks in the REGION itself.  */
761
 
762
VEC (basic_block, heap) *
763
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
764
                         unsigned n_region)
765
{
766
  unsigned i;
767
  basic_block dom;
768
  VEC (basic_block, heap) *doms = NULL;
769
 
770
  for (i = 0; i < n_region; i++)
771
    region[i]->flags |= BB_DUPLICATED;
772
  for (i = 0; i < n_region; i++)
773
    for (dom = first_dom_son (dir, region[i]);
774
         dom;
775
         dom = next_dom_son (dir, dom))
776
      if (!(dom->flags & BB_DUPLICATED))
777
        VEC_safe_push (basic_block, heap, doms, dom);
778
  for (i = 0; i < n_region; i++)
779
    region[i]->flags &= ~BB_DUPLICATED;
780
 
781
  return doms;
782
}
783
 
784
/* Returns the list of basic blocks including BB dominated by BB, in the
785
   direction DIR.  The vector will be sorted in preorder.  */
786
 
787
VEC (basic_block, heap) *
788
get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
789
{
790
  VEC(basic_block, heap) *bbs = NULL;
791
  unsigned i;
792
 
793
  i = 0;
794
  VEC_safe_push (basic_block, heap, bbs, bb);
795
 
796
  do
797
    {
798
      basic_block son;
799
 
800
      bb = VEC_index (basic_block, bbs, i++);
801
      for (son = first_dom_son (dir, bb);
802
           son;
803
           son = next_dom_son (dir, son))
804
        VEC_safe_push (basic_block, heap, bbs, son);
805
    }
806
  while (i < VEC_length (basic_block, bbs));
807
 
808
  return bbs;
809
}
810
 
811
/* Redirect all edges pointing to BB to TO.  */
812
void
813
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
814
                               basic_block to)
815
{
816
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
817
  struct et_node *bb_node, *to_node, *son;
818
 
819
  bb_node = bb->dom[dir_index];
820
  to_node = to->dom[dir_index];
821
 
822
  gcc_assert (dom_computed[dir_index]);
823
 
824
  if (!bb_node->son)
825
    return;
826
 
827
  while (bb_node->son)
828
    {
829
      son = bb_node->son;
830
 
831
      et_split (son);
832
      et_set_father (son, to_node);
833
    }
834
 
835
  if (dom_computed[dir_index] == DOM_OK)
836
    dom_computed[dir_index] = DOM_NO_FAST_QUERY;
837
}
838
 
839
/* Find first basic block in the tree dominating both BB1 and BB2.  */
840
basic_block
841
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
842
{
843
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
844
 
845
  gcc_assert (dom_computed[dir_index]);
846
 
847
  if (!bb1)
848
    return bb2;
849
  if (!bb2)
850
    return bb1;
851
 
852
  return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
853
}
854
 
855
 
856
/* Find the nearest common dominator for the basic blocks in BLOCKS,
857
   using dominance direction DIR.  */
858
 
859
basic_block
860
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
861
{
862
  unsigned i, first;
863
  bitmap_iterator bi;
864
  basic_block dom;
865
 
866
  first = bitmap_first_set_bit (blocks);
867
  dom = BASIC_BLOCK (first);
868
  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
869
    if (dom != BASIC_BLOCK (i))
870
      dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
871
 
872
  return dom;
873
}
874
 
875
/*  Given a dominator tree, we can determine whether one thing
876
    dominates another in constant time by using two DFS numbers:
877
 
878
    1. The number for when we visit a node on the way down the tree
879
    2. The number for when we visit a node on the way back up the tree
880
 
881
    You can view these as bounds for the range of dfs numbers the
882
    nodes in the subtree of the dominator tree rooted at that node
883
    will contain.
884
 
885
    The dominator tree is always a simple acyclic tree, so there are
886
    only three possible relations two nodes in the dominator tree have
887
    to each other:
888
 
889
    1. Node A is above Node B (and thus, Node A dominates node B)
890
 
891
     A
892
     |
893
     C
894
    / \
895
   B   D
896
 
897
 
898
   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
899
   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
900
   because we must hit A in the dominator tree *before* B on the walk
901
   down, and we will hit A *after* B on the walk back up
902
 
903
   2. Node A is below node B (and thus, node B dominates node A)
904
 
905
 
906
     B
907
     |
908
     A
909
    / \
910
   C   D
911
 
912
   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
913
   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
914
 
915
   This is because we must hit A in the dominator tree *after* B on
916
   the walk down, and we will hit A *before* B on the walk back up
917
 
918
   3. Node A and B are siblings (and thus, neither dominates the other)
919
 
920
     C
921
     |
922
     D
923
    / \
924
   A   B
925
 
926
   In the above case, DFS_Number_In of A will *always* be <=
927
   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
928
   DFS_Number_Out of B.  This is because we will always finish the dfs
929
   walk of one of the subtrees before the other, and thus, the dfs
930
   numbers for one subtree can't intersect with the range of dfs
931
   numbers for the other subtree.  If you swap A and B's position in
932
   the dominator tree, the comparison changes direction, but the point
933
   is that both comparisons will always go the same way if there is no
934
   dominance relationship.
935
 
936
   Thus, it is sufficient to write
937
 
938
   A_Dominates_B (node A, node B)
939
   {
940
     return DFS_Number_In(A) <= DFS_Number_In(B)
941
            && DFS_Number_Out (A) >= DFS_Number_Out(B);
942
   }
943
 
944
   A_Dominated_by_B (node A, node B)
945
   {
946
     return DFS_Number_In(A) >= DFS_Number_In(A)
947
            && DFS_Number_Out (A) <= DFS_Number_Out(B);
948
   }  */
949
 
950
/* Return TRUE in case BB1 is dominated by BB2.  */
951
bool
952
dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
953
{
954
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
955
  struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
956
 
957
  gcc_assert (dom_computed[dir_index]);
958
 
959
  if (dom_computed[dir_index] == DOM_OK)
960
    return (n1->dfs_num_in >= n2->dfs_num_in
961
            && n1->dfs_num_out <= n2->dfs_num_out);
962
 
963
  return et_below (n1, n2);
964
}
965
 
966
/* Returns the entry dfs number for basic block BB, in the direction DIR.  */
967
 
968
unsigned
969
bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
970
{
971
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
972
  struct et_node *n = bb->dom[dir_index];
973
 
974
  gcc_assert (dom_computed[dir_index] == DOM_OK);
975
  return n->dfs_num_in;
976
}
977
 
978
/* Returns the exit dfs number for basic block BB, in the direction DIR.  */
979
 
980
unsigned
981
bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
982
{
983
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
984
  struct et_node *n = bb->dom[dir_index];
985
 
986
  gcc_assert (dom_computed[dir_index] == DOM_OK);
987
  return n->dfs_num_out;
988
}
989
 
990
/* Verify invariants of dominator structure.  */
991
void
992
verify_dominators (enum cdi_direction dir)
993
{
994
  int err = 0;
995
  basic_block bb, imm_bb, imm_bb_correct;
996
  struct dom_info di;
997
  bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
998
 
999
  gcc_assert (dom_info_available_p (dir));
1000
 
1001
  init_dom_info (&di, dir);
1002
  calc_dfs_tree (&di, reverse);
1003
  calc_idoms (&di, reverse);
1004
 
1005
  FOR_EACH_BB (bb)
1006
    {
1007
      imm_bb = get_immediate_dominator (dir, bb);
1008
      if (!imm_bb)
1009
        {
1010
          error ("dominator of %d status unknown", bb->index);
1011
          err = 1;
1012
        }
1013
 
1014
      imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
1015
      if (imm_bb != imm_bb_correct)
1016
        {
1017
          error ("dominator of %d should be %d, not %d",
1018
                 bb->index, imm_bb_correct->index, imm_bb->index);
1019
          err = 1;
1020
        }
1021
    }
1022
 
1023
  free_dom_info (&di);
1024
  gcc_assert (!err);
1025
}
1026
 
1027
/* Determine immediate dominator (or postdominator, according to DIR) of BB,
1028
   assuming that dominators of other blocks are correct.  We also use it to
1029
   recompute the dominators in a restricted area, by iterating it until it
1030
   reaches a fixed point.  */
1031
 
1032
basic_block
1033
recompute_dominator (enum cdi_direction dir, basic_block bb)
1034
{
1035
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1036
  basic_block dom_bb = NULL;
1037
  edge e;
1038
  edge_iterator ei;
1039
 
1040
  gcc_assert (dom_computed[dir_index]);
1041
 
1042
  if (dir == CDI_DOMINATORS)
1043
    {
1044
      FOR_EACH_EDGE (e, ei, bb->preds)
1045
        {
1046
          if (!dominated_by_p (dir, e->src, bb))
1047
            dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1048
        }
1049
    }
1050
  else
1051
    {
1052
      FOR_EACH_EDGE (e, ei, bb->succs)
1053
        {
1054
          if (!dominated_by_p (dir, e->dest, bb))
1055
            dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1056
        }
1057
    }
1058
 
1059
  return dom_bb;
1060
}
1061
 
1062
/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1063
   of BBS.  We assume that all the immediate dominators except for those of the
1064
   blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
1065
   currently recorded immediate dominators of blocks in BBS really dominate the
1066
   blocks.  The basic blocks for that we determine the dominator are removed
1067
   from BBS.  */
1068
 
1069
static void
1070
prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
1071
                                bool conservative)
1072
{
1073
  unsigned i;
1074
  bool single;
1075
  basic_block bb, dom = NULL;
1076
  edge_iterator ei;
1077
  edge e;
1078
 
1079
  for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
1080
    {
1081
      if (bb == ENTRY_BLOCK_PTR)
1082
        goto succeed;
1083
 
1084
      if (single_pred_p (bb))
1085
        {
1086
          set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1087
          goto succeed;
1088
        }
1089
 
1090
      if (!conservative)
1091
        goto fail;
1092
 
1093
      single = true;
1094
      dom = NULL;
1095
      FOR_EACH_EDGE (e, ei, bb->preds)
1096
        {
1097
          if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1098
            continue;
1099
 
1100
          if (!dom)
1101
            dom = e->src;
1102
          else
1103
            {
1104
              single = false;
1105
              dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1106
            }
1107
        }
1108
 
1109
      gcc_assert (dom != NULL);
1110
      if (single
1111
          || find_edge (dom, bb))
1112
        {
1113
          set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1114
          goto succeed;
1115
        }
1116
 
1117
fail:
1118
      i++;
1119
      continue;
1120
 
1121
succeed:
1122
      VEC_unordered_remove (basic_block, bbs, i);
1123
    }
1124
}
1125
 
1126
/* Returns root of the dominance tree in the direction DIR that contains
1127
   BB.  */
1128
 
1129
static basic_block
1130
root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1131
{
1132
  return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1133
}
1134
 
1135
/* See the comment in iterate_fix_dominators.  Finds the immediate dominators
1136
   for the sons of Y, found using the SON and BROTHER arrays representing
1137
   the dominance tree of graph G.  BBS maps the vertices of G to the basic
1138
   blocks.  */
1139
 
1140
static void
1141
determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
1142
                               int y, int *son, int *brother)
1143
{
1144
  bitmap gprime;
1145
  int i, a, nc;
1146
  VEC (int, heap) **sccs;
1147
  basic_block bb, dom, ybb;
1148
  unsigned si;
1149
  edge e;
1150
  edge_iterator ei;
1151
 
1152
  if (son[y] == -1)
1153
    return;
1154
  if (y == (int) VEC_length (basic_block, bbs))
1155
    ybb = ENTRY_BLOCK_PTR;
1156
  else
1157
    ybb = VEC_index (basic_block, bbs, y);
1158
 
1159
  if (brother[son[y]] == -1)
1160
    {
1161
      /* Handle the common case Y has just one son specially.  */
1162
      bb = VEC_index (basic_block, bbs, son[y]);
1163
      set_immediate_dominator (CDI_DOMINATORS, bb,
1164
                               recompute_dominator (CDI_DOMINATORS, bb));
1165
      identify_vertices (g, y, son[y]);
1166
      return;
1167
    }
1168
 
1169
  gprime = BITMAP_ALLOC (NULL);
1170
  for (a = son[y]; a != -1; a = brother[a])
1171
    bitmap_set_bit (gprime, a);
1172
 
1173
  nc = graphds_scc (g, gprime);
1174
  BITMAP_FREE (gprime);
1175
 
1176
  sccs = XCNEWVEC (VEC (int, heap) *, nc);
1177
  for (a = son[y]; a != -1; a = brother[a])
1178
    VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
1179
 
1180
  for (i = nc - 1; i >= 0; i--)
1181
    {
1182
      dom = NULL;
1183
      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1184
        {
1185
          bb = VEC_index (basic_block, bbs, a);
1186
          FOR_EACH_EDGE (e, ei, bb->preds)
1187
            {
1188
              if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1189
                continue;
1190
 
1191
              dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1192
            }
1193
        }
1194
 
1195
      gcc_assert (dom != NULL);
1196
      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1197
        {
1198
          bb = VEC_index (basic_block, bbs, a);
1199
          set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1200
        }
1201
    }
1202
 
1203
  for (i = 0; i < nc; i++)
1204
    VEC_free (int, heap, sccs[i]);
1205
  free (sccs);
1206
 
1207
  for (a = son[y]; a != -1; a = brother[a])
1208
    identify_vertices (g, y, a);
1209
}
1210
 
1211
/* Recompute dominance information for basic blocks in the set BBS.  The
1212
   function assumes that the immediate dominators of all the other blocks
1213
   in CFG are correct, and that there are no unreachable blocks.
1214
 
1215
   If CONSERVATIVE is true, we additionally assume that all the ancestors of
1216
   a block of BBS in the current dominance tree dominate it.  */
1217
 
1218
void
1219
iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
1220
                        bool conservative)
1221
{
1222
  unsigned i;
1223
  basic_block bb, dom;
1224
  struct graph *g;
1225
  int n, y;
1226
  size_t dom_i;
1227
  edge e;
1228
  edge_iterator ei;
1229
  struct pointer_map_t *map;
1230
  int *parent, *son, *brother;
1231
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1232
 
1233
  /* We only support updating dominators.  There are some problems with
1234
     updating postdominators (need to add fake edges from infinite loops
1235
     and noreturn functions), and since we do not currently use
1236
     iterate_fix_dominators for postdominators, any attempt to handle these
1237
     problems would be unused, untested, and almost surely buggy.  We keep
1238
     the DIR argument for consistency with the rest of the dominator analysis
1239
     interface.  */
1240
  gcc_assert (dir == CDI_DOMINATORS);
1241
  gcc_assert (dom_computed[dir_index]);
1242
 
1243
  /* The algorithm we use takes inspiration from the following papers, although
1244
     the details are quite different from any of them:
1245
 
1246
     [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1247
         Dominator Tree of a Reducible Flowgraph
1248
     [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1249
          dominator trees
1250
     [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1251
          Algorithm
1252
 
1253
     First, we use the following heuristics to decrease the size of the BBS
1254
     set:
1255
       a) if BB has a single predecessor, then its immediate dominator is this
1256
          predecessor
1257
       additionally, if CONSERVATIVE is true:
1258
       b) if all the predecessors of BB except for one (X) are dominated by BB,
1259
          then X is the immediate dominator of BB
1260
       c) if the nearest common ancestor of the predecessors of BB is X and
1261
          X -> BB is an edge in CFG, then X is the immediate dominator of BB
1262
 
1263
     Then, we need to establish the dominance relation among the basic blocks
1264
     in BBS.  We split the dominance tree by removing the immediate dominator
1265
     edges from BBS, creating a forest F.  We form a graph G whose vertices
1266
     are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1267
     X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1268
     whose root is X.  We then determine dominance tree of G.  Note that
1269
     for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1270
     In this step, we can use arbitrary algorithm to determine dominators.
1271
     We decided to prefer the algorithm [3] to the algorithm of
1272
     Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1273
     10 during gcc bootstrap), and [3] should perform better in this case.
1274
 
1275
     Finally, we need to determine the immediate dominators for the basic
1276
     blocks of BBS.  If the immediate dominator of X in G is Y, then
1277
     the immediate dominator of X in CFG belongs to the tree of F rooted in
1278
     Y.  We process the dominator tree T of G recursively, starting from leaves.
1279
     Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1280
     subtrees of the dominance tree of CFG rooted in X_i are already correct.
1281
     Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
1282
     the following observations:
1283
       (i) the immediate dominator of all blocks in a strongly connected
1284
           component of G' is the same
1285
       (ii) if X has no predecessors in G', then the immediate dominator of X
1286
            is the nearest common ancestor of the predecessors of X in the
1287
            subtree of F rooted in Y
1288
     Therefore, it suffices to find the topological ordering of G', and
1289
     process the nodes X_i in this order using the rules (i) and (ii).
1290
     Then, we contract all the nodes X_i with Y in G, so that the further
1291
     steps work correctly.  */
1292
 
1293
  if (!conservative)
1294
    {
1295
      /* Split the tree now.  If the idoms of blocks in BBS are not
1296
         conservatively correct, setting the dominators using the
1297
         heuristics in prune_bbs_to_update_dominators could
1298
         create cycles in the dominance "tree", and cause ICE.  */
1299
      for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1300
        set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1301
    }
1302
 
1303
  prune_bbs_to_update_dominators (bbs, conservative);
1304
  n = VEC_length (basic_block, bbs);
1305
 
1306
  if (n == 0)
1307
    return;
1308
 
1309
  if (n == 1)
1310
    {
1311
      bb = VEC_index (basic_block, bbs, 0);
1312
      set_immediate_dominator (CDI_DOMINATORS, bb,
1313
                               recompute_dominator (CDI_DOMINATORS, bb));
1314
      return;
1315
    }
1316
 
1317
  /* Construct the graph G.  */
1318
  map = pointer_map_create ();
1319
  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1320
    {
1321
      /* If the dominance tree is conservatively correct, split it now.  */
1322
      if (conservative)
1323
        set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1324
      *pointer_map_insert (map, bb) = (void *) (size_t) i;
1325
    }
1326
  *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
1327
 
1328
  g = new_graph (n + 1);
1329
  for (y = 0; y < g->n_vertices; y++)
1330
    g->vertices[y].data = BITMAP_ALLOC (NULL);
1331
  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1332
    {
1333
      FOR_EACH_EDGE (e, ei, bb->preds)
1334
        {
1335
          dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1336
          if (dom == bb)
1337
            continue;
1338
 
1339
          dom_i = (size_t) *pointer_map_contains (map, dom);
1340
 
1341
          /* Do not include parallel edges to G.  */
1342
          if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
1343
            continue;
1344
 
1345
          bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
1346
          add_edge (g, dom_i, i);
1347
        }
1348
    }
1349
  for (y = 0; y < g->n_vertices; y++)
1350
    BITMAP_FREE (g->vertices[y].data);
1351
  pointer_map_destroy (map);
1352
 
1353
  /* Find the dominator tree of G.  */
1354
  son = XNEWVEC (int, n + 1);
1355
  brother = XNEWVEC (int, n + 1);
1356
  parent = XNEWVEC (int, n + 1);
1357
  graphds_domtree (g, n, parent, son, brother);
1358
 
1359
  /* Finally, traverse the tree and find the immediate dominators.  */
1360
  for (y = n; son[y] != -1; y = son[y])
1361
    continue;
1362
  while (y != -1)
1363
    {
1364
      determine_dominators_for_sons (g, bbs, y, son, brother);
1365
 
1366
      if (brother[y] != -1)
1367
        {
1368
          y = brother[y];
1369
          while (son[y] != -1)
1370
            y = son[y];
1371
        }
1372
      else
1373
        y = parent[y];
1374
    }
1375
 
1376
  free (son);
1377
  free (brother);
1378
  free (parent);
1379
 
1380
  free_graph (g);
1381
}
1382
 
1383
void
1384
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1385
{
1386
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1387
 
1388
  gcc_assert (dom_computed[dir_index]);
1389
  gcc_assert (!bb->dom[dir_index]);
1390
 
1391
  n_bbs_in_dom_tree[dir_index]++;
1392
 
1393
  bb->dom[dir_index] = et_new_tree (bb);
1394
 
1395
  if (dom_computed[dir_index] == DOM_OK)
1396
    dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1397
}
1398
 
1399
void
1400
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1401
{
1402
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1403
 
1404
  gcc_assert (dom_computed[dir_index]);
1405
 
1406
  et_free_tree (bb->dom[dir_index]);
1407
  bb->dom[dir_index] = NULL;
1408
  n_bbs_in_dom_tree[dir_index]--;
1409
 
1410
  if (dom_computed[dir_index] == DOM_OK)
1411
    dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1412
}
1413
 
1414
/* Returns the first son of BB in the dominator or postdominator tree
1415
   as determined by DIR.  */
1416
 
1417
basic_block
1418
first_dom_son (enum cdi_direction dir, basic_block bb)
1419
{
1420
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1421
  struct et_node *son = bb->dom[dir_index]->son;
1422
 
1423
  return (basic_block) (son ? son->data : NULL);
1424
}
1425
 
1426
/* Returns the next dominance son after BB in the dominator or postdominator
1427
   tree as determined by DIR, or NULL if it was the last one.  */
1428
 
1429
basic_block
1430
next_dom_son (enum cdi_direction dir, basic_block bb)
1431
{
1432
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1433
  struct et_node *next = bb->dom[dir_index]->right;
1434
 
1435
  return (basic_block) (next->father->son == next ? NULL : next->data);
1436
}
1437
 
1438
/* Return dominance availability for dominance info DIR.  */
1439
 
1440
enum dom_state
1441
dom_info_state (enum cdi_direction dir)
1442
{
1443
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1444
 
1445
  return dom_computed[dir_index];
1446
}
1447
 
1448
/* Set the dominance availability for dominance info DIR to NEW_STATE.  */
1449
 
1450
void
1451
set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1452
{
1453
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1454
 
1455
  dom_computed[dir_index] = new_state;
1456
}
1457
 
1458
/* Returns true if dominance information for direction DIR is available.  */
1459
 
1460
bool
1461
dom_info_available_p (enum cdi_direction dir)
1462
{
1463
  unsigned int dir_index = dom_convert_dir_to_idx (dir);
1464
 
1465
  return dom_computed[dir_index] != DOM_NONE;
1466
}
1467
 
1468
void
1469
debug_dominance_info (enum cdi_direction dir)
1470
{
1471
  basic_block bb, bb2;
1472
  FOR_EACH_BB (bb)
1473
    if ((bb2 = get_immediate_dominator (dir, bb)))
1474
      fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1475
}
1476
 
1477
/* Prints to stderr representation of the dominance tree (for direction DIR)
1478
   rooted in ROOT, indented by INDENT tabulators.  If INDENT_FIRST is false,
1479
   the first line of the output is not indented.  */
1480
 
1481
static void
1482
debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1483
                        unsigned indent, bool indent_first)
1484
{
1485
  basic_block son;
1486
  unsigned i;
1487
  bool first = true;
1488
 
1489
  if (indent_first)
1490
    for (i = 0; i < indent; i++)
1491
      fprintf (stderr, "\t");
1492
  fprintf (stderr, "%d\t", root->index);
1493
 
1494
  for (son = first_dom_son (dir, root);
1495
       son;
1496
       son = next_dom_son (dir, son))
1497
    {
1498
      debug_dominance_tree_1 (dir, son, indent + 1, !first);
1499
      first = false;
1500
    }
1501
 
1502
  if (first)
1503
    fprintf (stderr, "\n");
1504
}
1505
 
1506
/* Prints to stderr representation of the dominance tree (for direction DIR)
1507
   rooted in ROOT.  */
1508
 
1509
void
1510
debug_dominance_tree (enum cdi_direction dir, basic_block root)
1511
{
1512
  debug_dominance_tree_1 (dir, root, 0, false);
1513
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.