src/vm/jit/optimizing/dominators.cpp

   1 /* src/vm/jit/optimizing/dominators.cpp - dominators and dominance frontier
   2
   3    Copyright (C) 2005, 2006, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  21    02111-1307, USA.
  22
  23 */
  24
  25
  26 #include "config.h"
  27
  28 #include "config.h"
  29
  30 #include "mm/memory.h"
  31
  32 #include "toolbox/bitvector.h"
  33
  34 #include "vm/jit/jit.hpp"
  35
  36 #include "vm/jit/optimizing/graph.h"
  37 #include "vm/jit/optimizing/dominators.hpp"
  38
  39
  40 /* function prototypes */
  41 void dom_Dominators_init(dominatordata *dd, int basicblockcount);
  42 #ifdef DOM_DEBUG_CHECK
  43 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount);
  44 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount);
  45 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N,
  46                          int basicblockcount);
  47 #else
  48 int dom_AncestorWithLowestSemi(dominatordata *dd, int v);
  49 void dom_Link(dominatordata *dd, int p, int n);
  50 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N);
  51 #endif
  52
  53 /*************************************
  54 Calculate Dominators
  55 *************************************/
  56 dominatordata *compute_Dominators(graphdata *gd, int basicblockcount) {
  57         int i,j,n,N,p,s,s_,v,y;
  58         graphiterator iter;
  59         dominatordata *dd;
  60
  61         dd = (dominatordata*) DumpMemory::allocate(sizeof(dominatordata));
  62
  63         dom_Dominators_init(dd, basicblockcount);
  64
  65         N=0;
  66
  67         /* 1 ist the root node of the method                    */
  68         /* 0 is the artificial parent, where locals are set to their parameters */
  69         dom_DFS(gd, dd, -1, 0, &N
  70 #ifdef DOM_DEBUG_CHECK
  71                         ,basicblockcount
  72 #endif
  73                         );
  74
  75         for(i = N-1; i > 0; i--) {
  76                 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
  77                 n = dd->vertex[i];
  78                 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
  79                 p = dd->parent[n];
  80                 s = p;
  81                 j = graph_get_first_predecessor(gd, n, &iter);
  82                 for (; j != -1; j = graph_get_next(&iter)) {
  83                 _DOM_CHECK_BOUNDS(j, 0, basicblockcount);
  84                         if (dd->dfnum[j] <= dd->dfnum[n])
  85                                 s_ = j;
  86                         else
  87                                 s_ = dd->semi[dom_AncestorWithLowestSemi(dd, j
  88 #ifdef DOM_DEBUG_CHECK
  89                                                                                                                  ,basicblockcount
  90 #endif
  91                                                                                                                  )];
  92                 _DOM_CHECK_BOUNDS(s_, 0, basicblockcount);
  93                 _DOM_CHECK_BOUNDS(s, 0, basicblockcount);
  94                         if (dd->dfnum[s_] < dd->dfnum[s])
  95                                 s = s_;
  96                 }
  97                 dd->semi[n] = s;
  98                 _DOM_CHECK_BOUNDS(dd->num_bucket[s], 0, basicblockcount);
  99                 dd->bucket[s][dd->num_bucket[s]] = n;
 100                 dd->num_bucket[s]++;
 101                 dom_Link(dd, p, n
 102 #ifdef DOM_DEBUG_CHECK
 103                                  , basicblockcount
 104 #endif
 105                                  );
 106                 _DOM_CHECK_BOUNDS(p, 0, basicblockcount);
 107                 for(j = 0; j < dd->num_bucket[p]; j++) {
 108                 _DOM_CHECK_BOUNDS(j, 0, basicblockcount);
 109                         v = dd->bucket[p][j];
 110                         y = dom_AncestorWithLowestSemi(dd, v
 111 #ifdef DOM_DEBUG_CHECK
 112                                                                                    , basicblockcount
 113 #endif
 114                                                                                    );
 115                 _DOM_CHECK_BOUNDS(y, 0, basicblockcount);
 116                 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
 117             if (dd->semi[y] == dd->semi[v])
 118                                 dd->idom[v] = p;
 119                         else
 120                                 dd->samedom[v] = y;
 121                 }
 122                 dd->num_bucket[p] = 0;
 123         }
 124         for(i = 1; i < N; i++) {
 125                 n = dd->vertex[i];
 126                 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
 127             if (dd->samedom[n] != -1) {
 128                         _DOM_CHECK_BOUNDS(dd->samedom[n], 0, basicblockcount);
 129                         dd->idom[n] = dd->idom[dd->samedom[n]];
 130                 }
 131         }
 132         return dd;
 133 }
 134
 135 /********************************************
 136 compute Dominace Frontier
 137 ********************************************/
 138 void computeDF(graphdata *gd, dominatordata *dd, int basicblockcount, int n) {
 139         int c,i,j;
 140         bool *_S;
 141         graphiterator iter;
 142
 143         _S = (bool*) DumpMemory::allocate(sizeof(bool) * basicblockcount);
 144         for(i = 0; i < basicblockcount; i++)
 145                 _S[i] = false;
 146         i = graph_get_first_successor(gd, n, &iter);
 147         for (; i != -1; i = graph_get_next(&iter)) {
 148                 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
 149                 if (dd->idom[i] != n)
 150                         _S[i] = true;
 151         }
 152         for(c=0; c < basicblockcount; c++) {
 153                 if (dd->idom[c] == n) {
 154                         computeDF(gd, dd, basicblockcount, c);
 155                         for(j=0; j < dd->num_DF[c]; j++) {
 156                 _DOM_CHECK_BOUNDS(dd->DF[c][j], 0, basicblockcount);
 157                     if (n != dd->idom[dd->DF[c][j]])
 158                                         /* n does not dominate DF[c][j] -> traverse idom list? */
 159                                         _S[dd->DF[c][j]] = true;
 160                         }
 161                 }
 162         }
 163         for(i = 0; i < basicblockcount; i++)
 164                 if (_S[i]) {
 165                 _DOM_CHECK_BOUNDS(dd->num_DF[n], 0, basicblockcount);
 166                         dd->DF[n][dd->num_DF[n]] = i;
 167                         dd->num_DF[n]++;
 168                 }
 169 }
 170
 171
 172 void dom_Dominators_init(dominatordata *dd, int basicblockcount) {
 173         int i;
 174
 175         dd->dfnum      = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 176         dd->vertex     = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 177         dd->parent     = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 178         dd->semi       = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 179         dd->ancestor   = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 180         dd->idom       = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 181         dd->samedom    = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 182         dd->bucket     = (int**) DumpMemory::allocate(sizeof(int*) * basicblockcount);
 183         dd->num_bucket = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 184         dd->DF         = (int**) DumpMemory::allocate(sizeof(int*) * basicblockcount);
 185         dd->num_DF     = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 186         dd->best       = (int*)  DumpMemory::allocate(sizeof(int) * basicblockcount);
 187         for (i=0; i < basicblockcount; i++) {
 188                 dd->dfnum[i] = -1;
 189                 dd->semi[i] = dd->ancestor[i] = dd->idom[i] = dd->samedom[i] = -1;
 190                 dd->num_bucket[i] = 0;
 191                 dd->bucket[i] = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
 192                 dd->num_DF[i] = 0;
 193                 dd->DF[i] = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
 194         }
 195 }
 196
 197 /**************************************
 198 Create Depth First Spanning Tree
 199 **************************************/
 200 #ifdef DOM_DEBUG_CHECK
 201 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N,
 202                          int basicblockcount) {
 203 #else
 204 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N) {
 205 #endif
 206     int i;
 207         graphiterator iter;
 208
 209         _DOM_CHECK_BOUNDS(n,0,basicblockcount);
 210         if (dd->dfnum[n] == -1) { /* not visited till now? */
 211                 dd->dfnum[n] = *N;
 212                 _DOM_CHECK_BOUNDS(*N,0,basicblockcount);
 213                 dd->vertex[*N] = n;
 214                 dd->parent[n] = p;
 215                 (*N)++;
 216                 i = graph_get_first_successor(gd, n, &iter);
 217                 for (; i != -1; i = graph_get_next(&iter)) {
 218                         dom_DFS(gd, dd, n, i, N
 219 #ifdef DOM_DEBUG_CHECK
 220                                         , basicblockcount
 221 #endif
 222                                         );
 223                 }
 224         }
 225 }
 226
 227 #ifdef DOM_DEBUG_CHECK
 228 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount) {
 229 #else
 230 int dom_AncestorWithLowestSemi(dominatordata *dd, int v) {
 231 #endif
 232         int a,b;
 233
 234         _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
 235         a = dd->ancestor[v];
 236         _DOM_CHECK_BOUNDS(a,0,basicblockcount);
 237         if (dd->ancestor[a] != -1) {
 238                 b = dom_AncestorWithLowestSemi(dd, a
 239 #ifdef DOM_DEBUG_CHECK
 240                                                                            , basicblockcount
 241 #endif
 242                                                                            );
 243                 dd->ancestor[v] = dd->ancestor[a];
 244                 _DOM_CHECK_BOUNDS(b,0,basicblockcount);
 245                 _DOM_CHECK_BOUNDS(dd->best[v],0,basicblockcount);
 246                 _DOM_CHECK_BOUNDS(dd->semi[dd->best[v]],0,basicblockcount);
 247                 if (dd->dfnum[dd->semi[b]] < dd->dfnum[dd->semi[dd->best[v]]])
 248                         dd->best[v] = b;
 249         }
 250         return dd->best[v];
 251 }
 252
 253 #ifdef DOM_DEBUG_CHECK
 254 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount) {
 255 #else
 256 void dom_Link(dominatordata *dd, int p, int n) {
 257 #endif
 258         _DOM_CHECK_BOUNDS(n,0,basicblockcount);
 259         dd->ancestor[n] = p;
 260         dd->best[n] = n;
 261 }
 262
 263 /*********************************************************/
 264
 265 typedef struct basicblock_info basicblock_info;
 266
 267 struct basicblock_info {
 268         basicblock *bb;
 269         int dfnum;
 270         basicblock_info *parent;
 271         basicblock_info *semi;
 272         basicblock_info *ancestor;
 273         basicblock_info *best;
 274         basicblock_info *idom;
 275         basicblock_info *samedom;
 276         basicblock_info **bucket;
 277         unsigned bucketcount;
 278 };
 279
 280 typedef struct dominator_tree_info dominator_tree_info;
 281
 282 struct dominator_tree_info {
 283         jitdata *jd;
 284         basicblock_info *basicblocks;
 285         basicblock_info **df_map;
 286         unsigned df_counter;
 287 };
 288
 289 static dominator_tree_info *dominator_tree_init(jitdata *jd) {
 290         dominator_tree_info *di;
 291         basicblock *itb;
 292         basicblock_info *iti;
 293
 294         di = (dominator_tree_info*) DumpMemory::allocate(sizeof(dominator_tree_info));
 295
 296         di->jd = jd;
 297
 298         di->basicblocks = (basicblock_info*) DumpMemory::allocate(sizeof(basicblock_info) * jd->basicblockcount);
 299         MZERO(di->basicblocks, basicblock_info, jd->basicblockcount);
 300
 301         for (iti = di->basicblocks; iti != di->basicblocks + jd->basicblockcount; ++iti) {
 302                 iti->dfnum = -1;
 303                 iti->bucket = (basicblock_info**) DumpMemory::allocate(sizeof(basicblock_info*) * jd->basicblockcount);
 304                 iti->bucketcount = 0;
 305         }
 306
 307         for (itb = jd->basicblocks; itb; itb = itb->next) {
 308                 di->basicblocks[itb->nr].bb = itb;
 309         }
 310
 311         di->df_map = (basicblock_info**) DumpMemory::allocate(sizeof(basicblock_info*) * jd->basicblockcount);
 312         MZERO(di->df_map, basicblock_info *, jd->basicblockcount);
 313
 314         di->df_counter = 0;
 315
 316         return di;
 317 }
 318
 319 static inline basicblock_info *dominator_tree_get_basicblock(dominator_tree_info *di, basicblock *bb) {
 320         return di->basicblocks + bb->nr;
 321 }
 322
 323 static void dominator_tree_depth_first_search(
 324         dominator_tree_info *di, basicblock_info *parent, basicblock_info *node
 325 ) {
 326         basicblock **it;
 327
 328         if (node->dfnum == -1) {
 329
 330                 node->dfnum = di->df_counter;
 331                 node->parent = parent;
 332                 di->df_map[di->df_counter] = node;
 333                 di->df_counter += 1;
 334
 335                 for (it = node->bb->successors; it != node->bb->successors + node->bb->successorcount; ++it) {
 336                         dominator_tree_depth_first_search(
 337                                 di, node,
 338                                 dominator_tree_get_basicblock(di, *it)
 339                         );
 340                 }
 341         }
 342 }
 343
 344 void dominator_tree_link(dominator_tree_info *di, basicblock_info *parent, basicblock_info *node) {
 345         node->ancestor = parent;
 346         node->best = node;
 347 }
 348
 349 basicblock_info *dominator_tree_ancestor_with_lowest_semi(
 350         dominator_tree_info *di, basicblock_info *node
 351 ) {
 352         basicblock_info *a, *b;
 353
 354         a = node->ancestor;
 355
 356         if (a->ancestor != NULL) {
 357                 b = dominator_tree_ancestor_with_lowest_semi(di, a);
 358                 node->ancestor = a->ancestor;
 359                 if (b->semi->dfnum < node->best->semi->dfnum) {
 360                         node->best = b;
 361                 }
 362         }
 363
 364         return node->best;
 365 }
 366
 367 void dominator_tree_build_intern(jitdata *jd) {
 368
 369         dominator_tree_info *di;
 370         basicblock_info *node;
 371         basicblock_info *semicand;
 372         basicblock_info *pred;
 373         basicblock **itb;
 374         basicblock_info **itii;
 375         basicblock_info *v, *y;
 376         int i;
 377
 378         di = dominator_tree_init(jd);
 379
 380         dominator_tree_depth_first_search(di, NULL, dominator_tree_get_basicblock(di, jd->basicblocks));
 381
 382         for (i = di->df_counter - 1; i >= 1; --i) {
 383                 node = di->df_map[i];
 384
 385                 node->semi = node->parent;
 386
 387                 for (
 388                         itb = node->bb->predecessors;
 389                         itb != node->bb->predecessors + node->bb->predecessorcount;
 390                         ++itb
 391                 ) {
 392
 393                         pred = dominator_tree_get_basicblock(di, *itb);
 394
 395                         if (pred->dfnum <= node->dfnum) {
 396                                 semicand = pred;
 397                         } else {
 398                                 semicand = dominator_tree_ancestor_with_lowest_semi(di, pred)->semi;
 399                         }
 400
 401                         if (semicand->dfnum < node->semi->dfnum) {
 402                                 node->semi = semicand;
 403                         }
 404                 }
 405
 406                 node->semi->bucket[node->semi->bucketcount] = node;
 407                 node->semi->bucketcount += 1;
 408
 409                 dominator_tree_link(di, node->parent, node);
 410
 411                 for (itii = node->parent->bucket; itii != node->parent->bucket + node->parent->bucketcount; ++itii) {
 412                         v = *itii;
 413                         y = dominator_tree_ancestor_with_lowest_semi(di, v);
 414                         if (y->semi == v->semi) {
 415                                 v->idom = node->parent;
 416                         } else {
 417                                 v->samedom = y;
 418                         }
 419                 }
 420
 421                 node->parent->bucketcount = 0;
 422         }
 423
 424         for (i = 1; i < di->df_counter; ++i) {
 425                 node = di->df_map[i];
 426                 if (node->samedom) {
 427                         node->idom = node->samedom->idom;
 428                 }
 429
 430                 node->bb->idom = node->idom->bb;
 431                 node->idom->bb->domsuccessorcount += 1;
 432         }
 433 }
 434
 435 void dominator_tree_link_children(jitdata *jd) {
 436         basicblock *bb;
 437         /* basicblock number => current number of successors */
 438         unsigned *numsuccessors;
 439
 440         // Create new dump memory area.
 441         DumpMemoryArea dma;
 442
 443         /* Allocate memory for successors */
 444
 445         for (bb = jd->basicblocks; bb; bb = bb->next) {
 446                 if (bb->domsuccessorcount > 0) {
 447                         bb->domsuccessors = (basicblock**) DumpMemory::allocate(sizeof(basicblock*) * bb->domsuccessorcount);
 448                 }
 449         }
 450
 451         /* Allocate memory for per basic block counter of successors */
 452
 453         numsuccessors = (unsigned*) DumpMemory::allocate(sizeof(unsigned) * jd->basicblockcount);
 454         MZERO(numsuccessors, unsigned, jd->basicblockcount);
 455
 456         /* Link immediate dominators with successors */
 457
 458         for (bb = jd->basicblocks; bb; bb = bb->next) {
 459                 if (bb->idom) {
 460                         bb->idom->domsuccessors[numsuccessors[bb->idom->nr]] = bb;
 461                         numsuccessors[bb->idom->nr] += 1;
 462                 }
 463         }
 464 }
 465
 466 bool dominator_tree_build(jitdata *jd) {
 467         // Create new dump memory area.
 468         DumpMemoryArea dma;
 469
 470         dominator_tree_build_intern(jd);
 471
 472         dominator_tree_link_children(jd);
 473
 474         return true;
 475 }
 476
 477 typedef struct dominance_frontier_item dominance_frontier_item;
 478
 479 struct dominance_frontier_item {
 480         basicblock *bb;
 481         dominance_frontier_item *next;
 482 };
 483
 484 typedef struct dominance_frontier_list dominance_frontier_list;
 485
 486 struct dominance_frontier_list {
 487         dominance_frontier_item *first;
 488         unsigned count;
 489 };
 490
 491 void dominance_frontier_list_add(dominance_frontier_list *list, basicblock *bb) {
 492         dominance_frontier_item *item;
 493
 494         for (item = list->first; item; item = item->next) {
 495                 if (item->bb == bb) return;
 496         }
 497
 498         item = (dominance_frontier_item*) DumpMemory::allocate(sizeof(dominance_frontier_item));
 499         item->bb = bb;
 500         item->next = list->first;
 501         list->first = item;
 502         list->count += 1;
 503 }
 504
 505 typedef struct dominance_frontier_info dominance_frontier_info;
 506
 507 struct dominance_frontier_info {
 508         jitdata *jd;
 509         dominance_frontier_list *map;
 510 };
 511
 512 dominance_frontier_info *dominance_frontier_init(jitdata *jd) {
 513         dominance_frontier_info *dfi = (dominance_frontier_info*) DumpMemory::allocate(sizeof(dominance_frontier_info));
 514
 515         dfi->jd = jd;
 516
 517         dfi->map = (dominance_frontier_list*) DumpMemory::allocate(sizeof(dominance_frontier_list) * jd->basicblockcount);
 518         MZERO(dfi->map, dominance_frontier_list, jd->basicblockcount);
 519
 520         return dfi;
 521 }
 522
 523 bool dominance_frontier_dominates(basicblock *d, basicblock *x) {
 524         x = x->idom;
 525
 526         while (x != NULL) {
 527                 if (x == d) {
 528                         return true;
 529                 }
 530                 x = x->idom;
 531         }
 532
 533         return false;
 534 }
 535
 536 void dominance_frontier_for_block(dominance_frontier_info *dfi, basicblock *b) {
 537         basicblock **it;
 538         dominance_frontier_item *itdf;
 539         dominance_frontier_list s = { NULL, 0 };
 540
 541         for (it = b->successors; it != b->successors + b->successorcount; ++it) {
 542                 if ((*it)->idom != b) {
 543                         dominance_frontier_list_add(&s, *it);
 544                 }
 545         }
 546
 547         for (it = b->domsuccessors; it != b->domsuccessors + b->domsuccessorcount; ++it) {
 548                 dominance_frontier_for_block(dfi, *it);
 549                 for (itdf = dfi->map[(*it)->nr].first; itdf; itdf = itdf->next) {
 550                         if (! dominance_frontier_dominates(b, itdf->bb)) {
 551                                 dominance_frontier_list_add(&s, itdf->bb);
 552                         }
 553                 }
 554         }
 555
 556         dfi->map[b->nr] = s;
 557 }
 558
 559 void dominance_frontier_store(dominance_frontier_info *dfi) {
 560         basicblock *bb;
 561         dominance_frontier_item *itdf;
 562         basicblock **itout;
 563
 564         for (bb = dfi->jd->basicblocks; bb; bb = bb->next) {
 565                 if (bb->nr < dfi->jd->basicblockcount) {
 566                         if (dfi->map[bb->nr].count > 0) {
 567                                 bb->domfrontiercount = dfi->map[bb->nr].count;
 568                                 itout = bb->domfrontier = (basicblock**) DumpMemory::allocate(sizeof(basicblock*) * bb->domfrontiercount);
 569                                 for (itdf = dfi->map[bb->nr].first; itdf; itdf = itdf->next) {
 570                                         *itout = itdf->bb;
 571                                         itout += 1;
 572                                 }
 573                         }
 574                 }
 575         }
 576 }
 577
 578 bool dominance_frontier_build(jitdata *jd) {
 579         // Create new dump memory area.
 580         DumpMemoryArea dma;
 581
 582         dominance_frontier_info *dfi = dominance_frontier_init(jd);
 583         dominance_frontier_for_block(dfi, jd->basicblocks);
 584         dominance_frontier_store(dfi);
 585 }
 586
 587 #include "vm/jit/show.hpp"
 588 #include "vm/jit/python.h"
 589
 590 extern "C" void graph_add_edge( graphdata *gd, int from, int to );
 591
 592 void dominator_tree_validate(jitdata *jd, dominatordata *_dd) {
 593         graphdata *gd;
 594         int i, j;
 595         basicblock *bptr, **it;
 596         dominatordata *dd;
 597         int *itnr;
 598         bool found;
 599
 600         // Create new dump memory area.
 601         DumpMemoryArea dma;
 602
 603         fprintf(stderr, "%s/%s: \n", jd->m->clazz->name->text, jd->m->name->text);
 604         gd = graph_init(jd->basicblockcount);
 605
 606         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 607                 for (it = bptr->successors; it != bptr->successors + bptr->successorcount; ++it) {
 608                         graph_add_edge(gd, bptr->nr, (*it)->nr);
 609                 }
 610         }
 611
 612         dd = compute_Dominators(gd, jd->basicblockcount);
 613
 614         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 615                 if (bptr->flags >= BBREACHED) {
 616                         if (bptr->idom == NULL) {
 617                                 if (!(dd->idom[bptr->nr] == -1)) {
 618                                         printf("-- %d %d\n", dd->idom[bptr->nr], bptr->nr);
 619                                         assert(0);
 620                                 }
 621                         } else {
 622                                 assert(dd->idom[bptr->nr] == bptr->idom->nr);
 623                         }
 624                 }
 625         }
 626
 627         computeDF(gd, dd, jd->basicblockcount, 0);
 628
 629         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 630                 if (bptr->flags >= BBREACHED) {
 631                         assert(bptr->domfrontiercount == dd->num_DF[bptr->nr]);
 632                         for (itnr = dd->DF[bptr->nr]; itnr != dd->DF[bptr->nr] + dd->num_DF[bptr->nr]; ++itnr) {
 633                                 found = false;
 634                                 for (it = bptr->domfrontier; it != bptr->domfrontier + bptr->domfrontiercount; ++it) {
 635                                         if ((*it)->nr == *itnr) {
 636                                                 found =true; break;
 637                                         }
 638                                 }
 639                                 assert(found);
 640                         }
 641                 }
 642         }
 643 }
 644
 645
 646 /*
 647  * These are local overrides for various environment variables in Emacs.
 648  * Please do not remove this and leave it at the end of the file, where
 649  * Emacs will automagically detect them.
 650  * ---------------------------------------------------------------------
 651  * Local variables:
 652  * mode: c++
 653  * indent-tabs-mode: t
 654  * c-basic-offset: 4
 655  * tab-width: 4
 656  * End:
 657  */