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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [dominance.c] - Blame information for rev 684

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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