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