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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [dominance.c] - Blame information for rev 841

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Calculate (post)dominators in slightly super-linear time.
2
   Copyright (C) 2000, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3
   Contributed by Michael Matz (matz@ifh.de).
4
 
5
   This file is part of GCC.
6
 
7
   GCC is free software; you can redistribute it and/or modify it
8
   under the terms of the GNU General Public License as published by
9
   the Free Software Foundation; either version 3, or (at your option)
10
   any later version.
11
 
12
   GCC is distributed in the hope that it will be useful, but WITHOUT
13
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14
   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
15
   License for more details.
16
 
17
   You should have received a copy of the GNU General Public License
18
   along with GCC; see the file COPYING3.  If not see
19
   <http://www.gnu.org/licenses/>.  */
20
 
21
/* This file implements the well known algorithm from Lengauer and Tarjan
22
   to compute the dominators in a control flow graph.  A basic block D is said
23
   to dominate another block X, when all paths from the entry node of the CFG
24
   to X go also over D.  The dominance relation is a transitive reflexive
25
   relation and its minimal transitive reduction is a tree, called the
26
   dominator tree.  So for each block X besides the entry block exists a
27
   block I(X), called the immediate dominator of X, which is the parent of X
28
   in the dominator tree.
29
 
30
   The algorithm computes this dominator tree implicitly by computing for
31
   each block its immediate dominator.  We use tree balancing and path
32
   compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
33
   slowly growing functional inverse of the Ackerman function.  */
34
 
35
#include "config.h"
36
#include "system.h"
37
#include "coretypes.h"
38
#include "tm.h"
39
#include "rtl.h"
40
#include "hard-reg-set.h"
41
#include "obstack.h"
42
#include "basic-block.h"
43
#include "toplev.h"
44
#include "et-forest.h"
45
#include "timevar.h"
46
 
47
/* Whether the dominators and the postdominators are available.  */
48
enum dom_state dom_computed[2];
49
 
50
/* We name our nodes with integers, beginning with 1.  Zero is reserved for
51
   'undefined' or 'end of list'.  The name of each node is given by the dfs
52
   number of the corresponding basic block.  Please note, that we include the
53
   artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
54
   support multiple entry points.  Its dfs number is of course 1.  */
55
 
56
/* Type of Basic Block aka. TBB */
57
typedef unsigned int TBB;
58
 
59
/* We work in a poor-mans object oriented fashion, and carry an instance of
60
   this structure through all our 'methods'.  It holds various arrays
61
   reflecting the (sub)structure of the flowgraph.  Most of them are of type
62
   TBB and are also indexed by TBB.  */
63
 
64
struct dom_info
65
{
66
  /* The parent of a node in the DFS tree.  */
67
  TBB *dfs_parent;
68
  /* For a node x key[x] is roughly the node nearest to the root from which
69
     exists a way to x only over nodes behind x.  Such a node is also called
70
     semidominator.  */
71
  TBB *key;
72
  /* The value in path_min[x] is the node y on the path from x to the root of
73
     the tree x is in with the smallest key[y].  */
74
  TBB *path_min;
75
  /* bucket[x] points to the first node of the set of nodes having x as key.  */
76
  TBB *bucket;
77
  /* And next_bucket[x] points to the next node.  */
78
  TBB *next_bucket;
79
  /* After the algorithm is done, dom[x] contains the immediate dominator
80
     of x.  */
81
  TBB *dom;
82
 
83
  /* The following few fields implement the structures needed for disjoint
84
     sets.  */
85
  /* set_chain[x] is the next node on the path from x to the representant
86
     of the set containing x.  If set_chain[x]==0 then x is a root.  */
87
  TBB *set_chain;
88
  /* set_size[x] is the number of elements in the set named by x.  */
89
  unsigned int *set_size;
90
  /* set_child[x] is used for balancing the tree representing a set.  It can
91
     be understood as the next sibling of x.  */
92
  TBB *set_child;
93
 
94
  /* If b is the number of a basic block (BB->index), dfs_order[b] is the
95
     number of that node in DFS order counted from 1.  This is an index
96
     into most of the other arrays in this structure.  */
97
  TBB *dfs_order;
98
  /* If x is the DFS-index of a node which corresponds with a basic block,
99
     dfs_to_bb[x] is that basic block.  Note, that in our structure there are
100
     more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
101
     is true for every basic block bb, but not the opposite.  */
102
  basic_block *dfs_to_bb;
103
 
104
  /* This is the next free DFS number when creating the DFS tree.  */
105
  unsigned int dfsnum;
106
  /* The number of nodes in the DFS tree (==dfsnum-1).  */
107
  unsigned int nodes;
108
 
109
  /* Blocks with bits set here have a fake edge to EXIT.  These are used
110
     to turn a DFS forest into a proper tree.  */
111
  bitmap fake_exit_edge;
112
};
113
 
114
static void init_dom_info (struct dom_info *, enum cdi_direction);
115
static void free_dom_info (struct dom_info *);
116
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block,
117
                                  enum cdi_direction);
118
static void calc_dfs_tree (struct dom_info *, enum cdi_direction);
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 *, enum cdi_direction);
123
void debug_dominance_info (enum cdi_direction);
124
 
125
/* Keeps track of the*/
126
static unsigned n_bbs_in_dom_tree[2];
127
 
128
/* Helper macro for allocating and initializing an array,
129
   for aesthetic reasons.  */
130
#define init_ar(var, type, num, content)                        \
131
  do                                                            \
132
    {                                                           \
133
      unsigned int i = 1;    /* Catch content == i.  */         \
134
      if (! (content))                                          \
135
        (var) = XCNEWVEC (type, num);                           \
136
      else                                                      \
137
        {                                                       \
138
          (var) = XNEWVEC (type, (num));                        \
139
          for (i = 0; i < num; i++)                              \
140
            (var)[i] = (content);                               \
141
        }                                                       \
142
    }                                                           \
143
  while (0)
144
 
145
/* Allocate all needed memory in a pessimistic fashion (so we round up).
146
   This initializes the contents of DI, which already must be allocated.  */
147
 
148
static void
149
init_dom_info (struct dom_info *di, enum cdi_direction dir)
150
{
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
  di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL;
171
}
172
 
173
#undef init_ar
174
 
175
/* Free all allocated memory in DI, but not DI itself.  */
176
 
177
static void
178
free_dom_info (struct dom_info *di)
179
{
180
  free (di->dfs_parent);
181
  free (di->path_min);
182
  free (di->key);
183
  free (di->dom);
184
  free (di->bucket);
185
  free (di->next_bucket);
186
  free (di->set_chain);
187
  free (di->set_size);
188
  free (di->set_child);
189
  free (di->dfs_order);
190
  free (di->dfs_to_bb);
191
  BITMAP_FREE (di->fake_exit_edge);
192
}
193
 
194
/* The nonrecursive variant of creating a DFS tree.  DI is our working
195
   structure, BB the starting basic block for this tree and REVERSE
196
   is true, if predecessors should be visited instead of successors of a
197
   node.  After this is done all nodes reachable from BB were visited, have
198
   assigned their dfs number and are linked together to form a tree.  */
199
 
200
static void
201
calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb,
202
                      enum cdi_direction reverse)
203
{
204
  /* We call this _only_ if bb is not already visited.  */
205
  edge e;
206
  TBB child_i, my_i = 0;
207
  edge_iterator *stack;
208
  edge_iterator ei, einext;
209
  int sp;
210
  /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
211
     problem).  */
212
  basic_block en_block;
213
  /* Ending block.  */
214
  basic_block ex_block;
215
 
216
  stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
217
  sp = 0;
218
 
219
  /* Initialize our border blocks, and the first edge.  */
220
  if (reverse)
221
    {
222
      ei = ei_start (bb->preds);
223
      en_block = EXIT_BLOCK_PTR;
224
      ex_block = ENTRY_BLOCK_PTR;
225
    }
226
  else
227
    {
228
      ei = ei_start (bb->succs);
229
      en_block = ENTRY_BLOCK_PTR;
230
      ex_block = EXIT_BLOCK_PTR;
231
    }
232
 
233
  /* When the stack is empty we break out of this loop.  */
234
  while (1)
235
    {
236
      basic_block bn;
237
 
238
      /* This loop traverses edges e in depth first manner, and fills the
239
         stack.  */
240
      while (!ei_end_p (ei))
241
        {
242
          e = ei_edge (ei);
243
 
244
          /* Deduce from E the current and the next block (BB and BN), and the
245
             next edge.  */
246
          if (reverse)
247
            {
248
              bn = e->src;
249
 
250
              /* If the next node BN is either already visited or a border
251
                 block the current edge is useless, and simply overwritten
252
                 with the next edge out of the current node.  */
253
              if (bn == ex_block || di->dfs_order[bn->index])
254
                {
255
                  ei_next (&ei);
256
                  continue;
257
                }
258
              bb = e->dest;
259
              einext = ei_start (bn->preds);
260
            }
261
          else
262
            {
263
              bn = e->dest;
264
              if (bn == ex_block || di->dfs_order[bn->index])
265
                {
266
                  ei_next (&ei);
267
                  continue;
268
                }
269
              bb = e->src;
270
              einext = ei_start (bn->succs);
271
            }
272
 
273
          gcc_assert (bn != en_block);
274
 
275
          /* Fill the DFS tree info calculatable _before_ recursing.  */
276
          if (bb != en_block)
277
            my_i = di->dfs_order[bb->index];
278
          else
279
            my_i = di->dfs_order[last_basic_block];
280
          child_i = di->dfs_order[bn->index] = di->dfsnum++;
281
          di->dfs_to_bb[child_i] = bn;
282
          di->dfs_parent[child_i] = my_i;
283
 
284
          /* Save the current point in the CFG on the stack, and recurse.  */
285
          stack[sp++] = ei;
286
          ei = einext;
287
        }
288
 
289
      if (!sp)
290
        break;
291
      ei = stack[--sp];
292
 
293
      /* OK.  The edge-list was exhausted, meaning normally we would
294
         end the recursion.  After returning from the recursive call,
295
         there were (may be) other statements which were run after a
296
         child node was completely considered by DFS.  Here is the
297
         point to do it in the non-recursive variant.
298
         E.g. The block just completed is in e->dest for forward DFS,
299
         the block not yet completed (the parent of the one above)
300
         in e->src.  This could be used e.g. for computing the number of
301
         descendants or the tree depth.  */
302
      ei_next (&ei);
303
    }
304
  free (stack);
305
}
306
 
307
/* The main entry for calculating the DFS tree or forest.  DI is our working
308
   structure and REVERSE is true, if we are interested in the reverse flow
309
   graph.  In that case the result is not necessarily a tree but a forest,
310
   because there may be nodes from which the EXIT_BLOCK is unreachable.  */
311
 
312
static void
313
calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
314
{
315
  /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
316
  basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
317
  di->dfs_order[last_basic_block] = di->dfsnum;
318
  di->dfs_to_bb[di->dfsnum] = begin;
319
  di->dfsnum++;
320
 
321
  calc_dfs_tree_nonrec (di, begin, reverse);
322
 
323
  if (reverse)
324
    {
325
      /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
326
         They are reverse-unreachable.  In the dom-case we disallow such
327
         nodes, but in post-dom we have to deal with them.
328
 
329
         There are two situations in which this occurs.  First, noreturn
330
         functions.  Second, infinite loops.  In the first case we need to
331
         pretend that there is an edge to the exit block.  In the second
332
         case, we wind up with a forest.  We need to process all noreturn
333
         blocks before we know if we've got any infinite loops.  */
334
 
335
      basic_block b;
336
      bool saw_unconnected = false;
337
 
338
      FOR_EACH_BB_REVERSE (b)
339
        {
340
          if (EDGE_COUNT (b->succs) > 0)
341
            {
342
              if (di->dfs_order[b->index] == 0)
343
                saw_unconnected = true;
344
              continue;
345
            }
346
          bitmap_set_bit (di->fake_exit_edge, b->index);
347
          di->dfs_order[b->index] = di->dfsnum;
348
          di->dfs_to_bb[di->dfsnum] = b;
349
          di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
350
          di->dfsnum++;
351
          calc_dfs_tree_nonrec (di, b, reverse);
352
        }
353
 
354
      if (saw_unconnected)
355
        {
356
          FOR_EACH_BB_REVERSE (b)
357
            {
358
              if (di->dfs_order[b->index])
359
                continue;
360
              bitmap_set_bit (di->fake_exit_edge, b->index);
361
              di->dfs_order[b->index] = di->dfsnum;
362
              di->dfs_to_bb[di->dfsnum] = b;
363
              di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
364
              di->dfsnum++;
365
              calc_dfs_tree_nonrec (di, b, reverse);
366
            }
367
        }
368
    }
369
 
370
  di->nodes = di->dfsnum - 1;
371
 
372
  /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
373
  gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
374
}
375
 
376
/* Compress the path from V to the root of its set and update path_min at the
377
   same time.  After compress(di, V) set_chain[V] is the root of the set V is
378
   in and path_min[V] is the node with the smallest key[] value on the path
379
   from V to that root.  */
380
 
381
static void
382
compress (struct dom_info *di, TBB v)
383
{
384
  /* Btw. It's not worth to unrecurse compress() as the depth is usually not
385
     greater than 5 even for huge graphs (I've not seen call depth > 4).
386
     Also performance wise compress() ranges _far_ behind eval().  */
387
  TBB parent = di->set_chain[v];
388
  if (di->set_chain[parent])
389
    {
390
      compress (di, parent);
391
      if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
392
        di->path_min[v] = di->path_min[parent];
393
      di->set_chain[v] = di->set_chain[parent];
394
    }
395
}
396
 
397
/* Compress the path from V to the set root of V if needed (when the root has
398
   changed since the last call).  Returns the node with the smallest key[]
399
   value on the path from V to the root.  */
400
 
401
static inline TBB
402
eval (struct dom_info *di, TBB v)
403
{
404
  /* The representant of the set V is in, also called root (as the set
405
     representation is a tree).  */
406
  TBB rep = di->set_chain[v];
407
 
408
  /* V itself is the root.  */
409
  if (!rep)
410
    return di->path_min[v];
411
 
412
  /* Compress only if necessary.  */
413
  if (di->set_chain[rep])
414
    {
415
      compress (di, v);
416
      rep = di->set_chain[v];
417
    }
418
 
419
  if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
420
    return di->path_min[v];
421
  else
422
    return di->path_min[rep];
423
}
424
 
425
/* This essentially merges the two sets of V and W, giving a single set with
426
   the new root V.  The internal representation of these disjoint sets is a
427
   balanced tree.  Currently link(V,W) is only used with V being the parent
428
   of W.  */
429
 
430
static void
431
link_roots (struct dom_info *di, TBB v, TBB w)
432
{
433
  TBB s = w;
434
 
435
  /* Rebalance the tree.  */
436
  while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
437
    {
438
      if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
439
          >= 2 * di->set_size[di->set_child[s]])
440
        {
441
          di->set_chain[di->set_child[s]] = s;
442
          di->set_child[s] = di->set_child[di->set_child[s]];
443
        }
444
      else
445
        {
446
          di->set_size[di->set_child[s]] = di->set_size[s];
447
          s = di->set_chain[s] = di->set_child[s];
448
        }
449
    }
450
 
451
  di->path_min[s] = di->path_min[w];
452
  di->set_size[v] += di->set_size[w];
453
  if (di->set_size[v] < 2 * di->set_size[w])
454
    {
455
      TBB tmp = s;
456
      s = di->set_child[v];
457
      di->set_child[v] = tmp;
458
    }
459
 
460
  /* Merge all subtrees.  */
461
  while (s)
462
    {
463
      di->set_chain[s] = v;
464
      s = di->set_child[s];
465
    }
466
}
467
 
468
/* This calculates the immediate dominators (or post-dominators if REVERSE is
469
   true).  DI is our working structure and should hold the DFS forest.
470
   On return the immediate dominator to node V is in di->dom[V].  */
471
 
472
static void
473
calc_idoms (struct dom_info *di, enum cdi_direction reverse)
474
{
475
  TBB v, w, k, par;
476
  basic_block en_block;
477
  edge_iterator ei, einext;
478
 
479
  if (reverse)
480
    en_block = EXIT_BLOCK_PTR;
481
  else
482
    en_block = ENTRY_BLOCK_PTR;
483
 
484
  /* Go backwards in DFS order, to first look at the leafs.  */
485
  v = di->nodes;
486
  while (v > 1)
487
    {
488
      basic_block bb = di->dfs_to_bb[v];
489
      edge e;
490
 
491
      par = di->dfs_parent[v];
492
      k = v;
493
 
494
      ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
495
 
496
      if (reverse)
497
        {
498
          /* If this block has a fake edge to exit, process that first.  */
499
          if (bitmap_bit_p (di->fake_exit_edge, bb->index))
500
            {
501
              einext = ei;
502
              einext.index = 0;
503
              goto do_fake_exit_edge;
504
            }
505
        }
506
 
507
      /* Search all direct predecessors for the smallest node with a path
508
         to them.  That way we have the smallest node with also a path to
509
         us only over nodes behind us.  In effect we search for our
510
         semidominator.  */
511
      while (!ei_end_p (ei))
512
        {
513
          TBB k1;
514
          basic_block b;
515
 
516
          e = ei_edge (ei);
517
          b = (reverse) ? e->dest : e->src;
518
          einext = ei;
519
          ei_next (&einext);
520
 
521
          if (b == en_block)
522
            {
523
            do_fake_exit_edge:
524
              k1 = di->dfs_order[last_basic_block];
525
            }
526
          else
527
            k1 = di->dfs_order[b->index];
528
 
529
          /* Call eval() only if really needed.  If k1 is above V in DFS tree,
530
             then we know, that eval(k1) == k1 and key[k1] == k1.  */
531
          if (k1 > v)
532
            k1 = di->key[eval (di, k1)];
533
          if (k1 < k)
534
            k = k1;
535
 
536
          ei = einext;
537
        }
538
 
539
      di->key[v] = k;
540
      link_roots (di, par, v);
541
      di->next_bucket[v] = di->bucket[k];
542
      di->bucket[k] = v;
543
 
544
      /* Transform semidominators into dominators.  */
545
      for (w = di->bucket[par]; w; w = di->next_bucket[w])
546
        {
547
          k = eval (di, w);
548
          if (di->key[k] < di->key[w])
549
            di->dom[w] = k;
550
          else
551
            di->dom[w] = par;
552
        }
553
      /* We don't need to cleanup next_bucket[].  */
554
      di->bucket[par] = 0;
555
      v--;
556
    }
557
 
558
  /* Explicitly define the dominators.  */
559
  di->dom[1] = 0;
560
  for (v = 2; v <= di->nodes; v++)
561
    if (di->dom[v] != di->key[v])
562
      di->dom[v] = di->dom[di->dom[v]];
563
}
564
 
565
/* Assign dfs numbers starting from NUM to NODE and its sons.  */
566
 
567
static void
568
assign_dfs_numbers (struct et_node *node, int *num)
569
{
570
  struct et_node *son;
571
 
572
  node->dfs_num_in = (*num)++;
573
 
574
  if (node->son)
575
    {
576
      assign_dfs_numbers (node->son, num);
577
      for (son = node->son->right; son != node->son; son = son->right)
578
        assign_dfs_numbers (son, num);
579
    }
580
 
581
  node->dfs_num_out = (*num)++;
582
}
583
 
584
/* Compute the data necessary for fast resolving of dominator queries in a
585
   static dominator tree.  */
586
 
587
static void
588
compute_dom_fast_query (enum cdi_direction dir)
589
{
590
  int num = 0;
591
  basic_block bb;
592
 
593
  gcc_assert (dom_info_available_p (dir));
594
 
595
  if (dom_computed[dir] == DOM_OK)
596
    return;
597
 
598
  FOR_ALL_BB (bb)
599
    {
600
      if (!bb->dom[dir]->father)
601
        assign_dfs_numbers (bb->dom[dir], &num);
602
    }
603
 
604
  dom_computed[dir] = DOM_OK;
605
}
606
 
607
/* The main entry point into this module.  DIR is set depending on whether
608
   we want to compute dominators or postdominators.  */
609
 
610
void
611
calculate_dominance_info (enum cdi_direction dir)
612
{
613
  struct dom_info di;
614
  basic_block b;
615
 
616
  if (dom_computed[dir] == DOM_OK)
617
    return;
618
 
619
  timevar_push (TV_DOMINANCE);
620
  if (!dom_info_available_p (dir))
621
    {
622
      gcc_assert (!n_bbs_in_dom_tree[dir]);
623
 
624
      FOR_ALL_BB (b)
625
        {
626
          b->dom[dir] = et_new_tree (b);
627
        }
628
      n_bbs_in_dom_tree[dir] = n_basic_blocks;
629
 
630
      init_dom_info (&di, dir);
631
      calc_dfs_tree (&di, dir);
632
      calc_idoms (&di, dir);
633
 
634
      FOR_EACH_BB (b)
635
        {
636
          TBB d = di.dom[di.dfs_order[b->index]];
637
 
638
          if (di.dfs_to_bb[d])
639
            et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]);
640
        }
641
 
642
      free_dom_info (&di);
643
      dom_computed[dir] = DOM_NO_FAST_QUERY;
644
    }
645
 
646
  compute_dom_fast_query (dir);
647
 
648
  timevar_pop (TV_DOMINANCE);
649
}
650
 
651
/* Free dominance information for direction DIR.  */
652
void
653
free_dominance_info (enum cdi_direction dir)
654
{
655
  basic_block bb;
656
 
657
  if (!dom_info_available_p (dir))
658
    return;
659
 
660
  FOR_ALL_BB (bb)
661
    {
662
      et_free_tree_force (bb->dom[dir]);
663
      bb->dom[dir] = NULL;
664
    }
665
  et_free_pools ();
666
 
667
  n_bbs_in_dom_tree[dir] = 0;
668
 
669
  dom_computed[dir] = DOM_NONE;
670
}
671
 
672
/* Return the immediate dominator of basic block BB.  */
673
basic_block
674
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
675
{
676
  struct et_node *node = bb->dom[dir];
677
 
678
  gcc_assert (dom_computed[dir]);
679
 
680
  if (!node->father)
681
    return NULL;
682
 
683
  return node->father->data;
684
}
685
 
686
/* Set the immediate dominator of the block possibly removing
687
   existing edge.  NULL can be used to remove any edge.  */
688
inline void
689
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
690
                         basic_block dominated_by)
691
{
692
  struct et_node *node = bb->dom[dir];
693
 
694
  gcc_assert (dom_computed[dir]);
695
 
696
  if (node->father)
697
    {
698
      if (node->father->data == dominated_by)
699
        return;
700
      et_split (node);
701
    }
702
 
703
  if (dominated_by)
704
    et_set_father (node, dominated_by->dom[dir]);
705
 
706
  if (dom_computed[dir] == DOM_OK)
707
    dom_computed[dir] = DOM_NO_FAST_QUERY;
708
}
709
 
710
/* Store all basic blocks immediately dominated by BB into BBS and return
711
   their number.  */
712
int
713
get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
714
{
715
  int n;
716
  struct et_node *node = bb->dom[dir], *son = node->son, *ason;
717
 
718
  gcc_assert (dom_computed[dir]);
719
 
720
  if (!son)
721
    {
722
      *bbs = NULL;
723
      return 0;
724
    }
725
 
726
  for (ason = son->right, n = 1; ason != son; ason = ason->right)
727
    n++;
728
 
729
  *bbs = XNEWVEC (basic_block, n);
730
  (*bbs)[0] = son->data;
731
  for (ason = son->right, n = 1; ason != son; ason = ason->right)
732
    (*bbs)[n++] = ason->data;
733
 
734
  return n;
735
}
736
 
737
/* Find all basic blocks that are immediately dominated (in direction DIR)
738
   by some block between N_REGION ones stored in REGION, except for blocks
739
   in the REGION itself.  The found blocks are stored to DOMS and their number
740
   is returned.  */
741
 
742
unsigned
743
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
744
                         unsigned n_region, basic_block *doms)
745
{
746
  unsigned n_doms = 0, i;
747
  basic_block dom;
748
 
749
  for (i = 0; i < n_region; i++)
750
    region[i]->flags |= BB_DUPLICATED;
751
  for (i = 0; i < n_region; i++)
752
    for (dom = first_dom_son (dir, region[i]);
753
         dom;
754
         dom = next_dom_son (dir, dom))
755
      if (!(dom->flags & BB_DUPLICATED))
756
        doms[n_doms++] = dom;
757
  for (i = 0; i < n_region; i++)
758
    region[i]->flags &= ~BB_DUPLICATED;
759
 
760
  return n_doms;
761
}
762
 
763
/* Redirect all edges pointing to BB to TO.  */
764
void
765
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
766
                               basic_block to)
767
{
768
  struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
769
 
770
  gcc_assert (dom_computed[dir]);
771
 
772
  if (!bb_node->son)
773
    return;
774
 
775
  while (bb_node->son)
776
    {
777
      son = bb_node->son;
778
 
779
      et_split (son);
780
      et_set_father (son, to_node);
781
    }
782
 
783
  if (dom_computed[dir] == DOM_OK)
784
    dom_computed[dir] = DOM_NO_FAST_QUERY;
785
}
786
 
787
/* Find first basic block in the tree dominating both BB1 and BB2.  */
788
basic_block
789
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
790
{
791
  gcc_assert (dom_computed[dir]);
792
 
793
  if (!bb1)
794
    return bb2;
795
  if (!bb2)
796
    return bb1;
797
 
798
  return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
799
}
800
 
801
 
802
/* Find the nearest common dominator for the basic blocks in BLOCKS,
803
   using dominance direction DIR.  */
804
 
805
basic_block
806
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
807
{
808
  unsigned i, first;
809
  bitmap_iterator bi;
810
  basic_block dom;
811
 
812
  first = bitmap_first_set_bit (blocks);
813
  dom = BASIC_BLOCK (first);
814
  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
815
    if (dom != BASIC_BLOCK (i))
816
      dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
817
 
818
  return dom;
819
}
820
 
821
/*  Given a dominator tree, we can determine whether one thing
822
    dominates another in constant time by using two DFS numbers:
823
 
824
    1. The number for when we visit a node on the way down the tree
825
    2. The number for when we visit a node on the way back up the tree
826
 
827
    You can view these as bounds for the range of dfs numbers the
828
    nodes in the subtree of the dominator tree rooted at that node
829
    will contain.
830
 
831
    The dominator tree is always a simple acyclic tree, so there are
832
    only three possible relations two nodes in the dominator tree have
833
    to each other:
834
 
835
    1. Node A is above Node B (and thus, Node A dominates node B)
836
 
837
     A
838
     |
839
     C
840
    / \
841
   B   D
842
 
843
 
844
   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
845
   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
846
   because we must hit A in the dominator tree *before* B on the walk
847
   down, and we will hit A *after* B on the walk back up
848
 
849
   2. Node A is below node B (and thus, node B dominates node A)
850
 
851
 
852
     B
853
     |
854
     A
855
    / \
856
   C   D
857
 
858
   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
859
   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
860
 
861
   This is because we must hit A in the dominator tree *after* B on
862
   the walk down, and we will hit A *before* B on the walk back up
863
 
864
   3. Node A and B are siblings (and thus, neither dominates the other)
865
 
866
     C
867
     |
868
     D
869
    / \
870
   A   B
871
 
872
   In the above case, DFS_Number_In of A will *always* be <=
873
   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
874
   DFS_Number_Out of B.  This is because we will always finish the dfs
875
   walk of one of the subtrees before the other, and thus, the dfs
876
   numbers for one subtree can't intersect with the range of dfs
877
   numbers for the other subtree.  If you swap A and B's position in
878
   the dominator tree, the comparison changes direction, but the point
879
   is that both comparisons will always go the same way if there is no
880
   dominance relationship.
881
 
882
   Thus, it is sufficient to write
883
 
884
   A_Dominates_B (node A, node B)
885
   {
886
     return DFS_Number_In(A) <= DFS_Number_In(B)
887
            && DFS_Number_Out (A) >= DFS_Number_Out(B);
888
   }
889
 
890
   A_Dominated_by_B (node A, node B)
891
   {
892
     return DFS_Number_In(A) >= DFS_Number_In(A)
893
            && DFS_Number_Out (A) <= DFS_Number_Out(B);
894
   }  */
895
 
896
/* Return TRUE in case BB1 is dominated by BB2.  */
897
bool
898
dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
899
{
900
  struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
901
 
902
  gcc_assert (dom_computed[dir]);
903
 
904
  if (dom_computed[dir] == DOM_OK)
905
    return (n1->dfs_num_in >= n2->dfs_num_in
906
            && n1->dfs_num_out <= n2->dfs_num_out);
907
 
908
  return et_below (n1, n2);
909
}
910
 
911
/* Returns the entry dfs number for basic block BB, in the direction DIR.  */
912
 
913
unsigned
914
bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
915
{
916
  struct et_node *n = bb->dom[dir];
917
 
918
  gcc_assert (dom_computed[dir] == DOM_OK);
919
  return n->dfs_num_in;
920
}
921
 
922
/* Returns the exit dfs number for basic block BB, in the direction DIR.  */
923
 
924
unsigned
925
bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
926
{
927
  struct et_node *n = bb->dom[dir];
928
 
929
  gcc_assert (dom_computed[dir] == DOM_OK);
930
  return n->dfs_num_out;
931
}
932
 
933
/* Verify invariants of dominator structure.  */
934
void
935
verify_dominators (enum cdi_direction dir)
936
{
937
  int err = 0;
938
  basic_block bb;
939
 
940
  gcc_assert (dom_info_available_p (dir));
941
 
942
  FOR_EACH_BB (bb)
943
    {
944
      basic_block dom_bb;
945
      basic_block imm_bb;
946
 
947
      dom_bb = recount_dominator (dir, bb);
948
      imm_bb = get_immediate_dominator (dir, bb);
949
      if (dom_bb != imm_bb)
950
        {
951
          if ((dom_bb == NULL) || (imm_bb == NULL))
952
            error ("dominator of %d status unknown", bb->index);
953
          else
954
            error ("dominator of %d should be %d, not %d",
955
                   bb->index, dom_bb->index, imm_bb->index);
956
          err = 1;
957
        }
958
    }
959
 
960
  if (dir == CDI_DOMINATORS)
961
    {
962
      FOR_EACH_BB (bb)
963
        {
964
          if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
965
            {
966
              error ("ENTRY does not dominate bb %d", bb->index);
967
              err = 1;
968
            }
969
        }
970
    }
971
 
972
  gcc_assert (!err);
973
}
974
 
975
/* Determine immediate dominator (or postdominator, according to DIR) of BB,
976
   assuming that dominators of other blocks are correct.  We also use it to
977
   recompute the dominators in a restricted area, by iterating it until it
978
   reaches a fixed point.  */
979
 
980
basic_block
981
recount_dominator (enum cdi_direction dir, basic_block bb)
982
{
983
  basic_block dom_bb = NULL;
984
  edge e;
985
  edge_iterator ei;
986
 
987
  gcc_assert (dom_computed[dir]);
988
 
989
  if (dir == CDI_DOMINATORS)
990
    {
991
      FOR_EACH_EDGE (e, ei, bb->preds)
992
        {
993
          /* Ignore the predecessors that either are not reachable from
994
             the entry block, or whose dominator was not determined yet.  */
995
          if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
996
            continue;
997
 
998
          if (!dominated_by_p (dir, e->src, bb))
999
            dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1000
        }
1001
    }
1002
  else
1003
    {
1004
      FOR_EACH_EDGE (e, ei, bb->succs)
1005
        {
1006
          if (!dominated_by_p (dir, e->dest, bb))
1007
            dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1008
        }
1009
    }
1010
 
1011
  return dom_bb;
1012
}
1013
 
1014
/* Iteratively recount dominators of BBS. The change is supposed to be local
1015
   and not to grow further.  */
1016
void
1017
iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
1018
{
1019
  int i, changed = 1;
1020
  basic_block old_dom, new_dom;
1021
 
1022
  gcc_assert (dom_computed[dir]);
1023
 
1024
  for (i = 0; i < n; i++)
1025
    set_immediate_dominator (dir, bbs[i], NULL);
1026
 
1027
  while (changed)
1028
    {
1029
      changed = 0;
1030
      for (i = 0; i < n; i++)
1031
        {
1032
          old_dom = get_immediate_dominator (dir, bbs[i]);
1033
          new_dom = recount_dominator (dir, bbs[i]);
1034
          if (old_dom != new_dom)
1035
            {
1036
              changed = 1;
1037
              set_immediate_dominator (dir, bbs[i], new_dom);
1038
            }
1039
        }
1040
    }
1041
 
1042
  for (i = 0; i < n; i++)
1043
    gcc_assert (get_immediate_dominator (dir, bbs[i]));
1044
}
1045
 
1046
void
1047
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1048
{
1049
  gcc_assert (dom_computed[dir]);
1050
  gcc_assert (!bb->dom[dir]);
1051
 
1052
  n_bbs_in_dom_tree[dir]++;
1053
 
1054
  bb->dom[dir] = et_new_tree (bb);
1055
 
1056
  if (dom_computed[dir] == DOM_OK)
1057
    dom_computed[dir] = DOM_NO_FAST_QUERY;
1058
}
1059
 
1060
void
1061
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1062
{
1063
  gcc_assert (dom_computed[dir]);
1064
 
1065
  et_free_tree (bb->dom[dir]);
1066
  bb->dom[dir] = NULL;
1067
  n_bbs_in_dom_tree[dir]--;
1068
 
1069
  if (dom_computed[dir] == DOM_OK)
1070
    dom_computed[dir] = DOM_NO_FAST_QUERY;
1071
}
1072
 
1073
/* Returns the first son of BB in the dominator or postdominator tree
1074
   as determined by DIR.  */
1075
 
1076
basic_block
1077
first_dom_son (enum cdi_direction dir, basic_block bb)
1078
{
1079
  struct et_node *son = bb->dom[dir]->son;
1080
 
1081
  return son ? son->data : NULL;
1082
}
1083
 
1084
/* Returns the next dominance son after BB in the dominator or postdominator
1085
   tree as determined by DIR, or NULL if it was the last one.  */
1086
 
1087
basic_block
1088
next_dom_son (enum cdi_direction dir, basic_block bb)
1089
{
1090
  struct et_node *next = bb->dom[dir]->right;
1091
 
1092
  return next->father->son == next ? NULL : next->data;
1093
}
1094
 
1095
/* Returns true if dominance information for direction DIR is available.  */
1096
 
1097
bool
1098
dom_info_available_p (enum cdi_direction dir)
1099
{
1100
  return dom_computed[dir] != DOM_NONE;
1101
}
1102
 
1103
void
1104
debug_dominance_info (enum cdi_direction dir)
1105
{
1106
  basic_block bb, bb2;
1107
  FOR_EACH_BB (bb)
1108
    if ((bb2 = get_immediate_dominator (dir, bb)))
1109
      fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1110
}

powered by: WebSVN 2.1.0

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