src/vm/jit/optimizing/dominators.c

   1 /* src/vm/jit/optimizing/dominators.c - dominators and dominance frontier
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29
  30 */
  31 #include "mm/memory.h"
  32
  33 #include "toolbox/bitvector.h"
  34
  35 #include "vm/jit/jit.h"
  36
  37 #include "vm/jit/optimizing/graph.h"
  38 #include "vm/jit/optimizing/dominators.h"
  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 = DNEW(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 = DMNEW(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  = DMNEW(int, basicblockcount);
 176         dd->vertex = DMNEW(int, basicblockcount);
 177         dd->parent = DMNEW(int, basicblockcount);
 178         dd->semi   = DMNEW(int, basicblockcount);
 179         dd->ancestor = DMNEW(int, basicblockcount);
 180         dd->idom     = DMNEW(int, basicblockcount);
 181         dd->samedom  = DMNEW(int, basicblockcount);
 182         dd->bucket   = DMNEW(int*, basicblockcount);
 183         dd->num_bucket = DMNEW(int, basicblockcount);
 184         dd->DF       = DMNEW(int*, basicblockcount);
 185         dd->num_DF   = DMNEW(int, basicblockcount);
 186         dd->best     = DMNEW(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] = DMNEW(int, basicblockcount);
 192                 dd->num_DF[i] = 0;
 193                 dd->DF[i] = DMNEW(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 = DNEW(dominator_tree_info);
 295
 296         di->jd = jd;
 297
 298         di->basicblocks = DMNEW(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 = DMNEW(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 = DMNEW(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 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         int32_t ds;
 438         /* basicblock number => current number of successors */
 439         unsigned *numsuccessors;
 440
 441         /* Allocate memory for successors */
 442
 443         for (bb = jd->basicblocks; bb; bb = bb->next) {
 444                 if (bb->domsuccessorcount > 0) {
 445                         bb->domsuccessors = DMNEW(basicblock *, bb->domsuccessorcount);
 446                 }
 447         }
 448
 449         /* Allocate memory for per basic block counter of successors */
 450
 451         ds = dumpmemory_marker();
 452         numsuccessors = DMNEW(unsigned, jd->basicblockcount);
 453         MZERO(numsuccessors, unsigned, jd->basicblockcount);
 454
 455         /* Link immediate dominators with successors */
 456
 457         for (bb = jd->basicblocks; bb; bb = bb->next) {
 458                 if (bb->idom) {
 459                         bb->idom->domsuccessors[numsuccessors[bb->idom->nr]] = bb;
 460                         numsuccessors[bb->idom->nr] += 1;
 461                 }
 462         }
 463
 464         /* Free memory */
 465
 466         dumpmemory_release(ds);
 467 }
 468
 469 bool dominator_tree_build(jitdata *jd) {
 470         int32_t ds;
 471
 472         ds = dumpmemory_marker();
 473         dominator_tree_build_intern(jd);
 474         dumpmemory_release(ds);
 475
 476         dominator_tree_link_children(jd);
 477
 478         return true;
 479 }
 480
 481 typedef struct dominance_frontier_item dominance_frontier_item;
 482
 483 struct dominance_frontier_item {
 484         basicblock *bb;
 485         dominance_frontier_item *next;
 486 };
 487
 488 typedef struct dominance_frontier_list dominance_frontier_list;
 489
 490 struct dominance_frontier_list {
 491         dominance_frontier_item *first;
 492         unsigned count;
 493 };
 494
 495 void dominance_frontier_list_add(dominance_frontier_list *list, basicblock *bb) {
 496         dominance_frontier_item *item;
 497
 498         for (item = list->first; item; item = item->next) {
 499                 if (item->bb == bb) return;
 500         }
 501
 502         item = DNEW(dominance_frontier_item);
 503         item->bb = bb;
 504         item->next = list->first;
 505         list->first = item;
 506         list->count += 1;
 507 }
 508
 509 typedef struct dominance_frontier_info dominance_frontier_info;
 510
 511 struct dominance_frontier_info {
 512         jitdata *jd;
 513         dominance_frontier_list *map;
 514 };
 515
 516 dominance_frontier_info *dominance_frontier_init(jitdata *jd) {
 517         dominance_frontier_info *dfi = DNEW(dominance_frontier_info);
 518
 519         dfi->jd = jd;
 520
 521         dfi->map = DMNEW(dominance_frontier_list, jd->basicblockcount);
 522         MZERO(dfi->map, dominance_frontier_list, jd->basicblockcount);
 523
 524         return dfi;
 525 }
 526
 527 bool dominance_frontier_dominates(basicblock *d, basicblock *x) {
 528         x = x->idom;
 529
 530         while (x != NULL) {
 531                 if (x == d) {
 532                         return true;
 533                 }
 534                 x = x->idom;
 535         }
 536
 537         return false;
 538 }
 539
 540 void dominance_frontier_for_block(dominance_frontier_info *dfi, basicblock *b) {
 541         basicblock **it;
 542         dominance_frontier_item *itdf;
 543         dominance_frontier_list s = { NULL, 0 };
 544
 545         for (it = b->successors; it != b->successors + b->successorcount; ++it) {
 546                 if ((*it)->idom != b) {
 547                         dominance_frontier_list_add(&s, *it);
 548                 }
 549         }
 550
 551         for (it = b->domsuccessors; it != b->domsuccessors + b->domsuccessorcount; ++it) {
 552                 dominance_frontier_for_block(dfi, *it);
 553                 for (itdf = dfi->map[(*it)->nr].first; itdf; itdf = itdf->next) {
 554                         if (! dominance_frontier_dominates(b, itdf->bb)) {
 555                                 dominance_frontier_list_add(&s, itdf->bb);
 556                         }
 557                 }
 558         }
 559
 560         dfi->map[b->nr] = s;
 561 }
 562
 563 void dominance_frontier_store(dominance_frontier_info *dfi) {
 564         basicblock *bb;
 565         dominance_frontier_item *itdf;
 566         basicblock **itout;
 567
 568         for (bb = dfi->jd->basicblocks; bb; bb = bb->next) {
 569                 if (bb->nr < dfi->jd->basicblockcount) {
 570                         if (dfi->map[bb->nr].count > 0) {
 571                                 bb->domfrontiercount = dfi->map[bb->nr].count;
 572                                 itout = bb->domfrontier = DMNEW(basicblock *, bb->domfrontiercount);
 573                                 for (itdf = dfi->map[bb->nr].first; itdf; itdf = itdf->next) {
 574                                         *itout = itdf->bb;
 575                                         itout += 1;
 576                                 }
 577                         }
 578                 }
 579         }
 580 }
 581
 582 bool dominance_frontier_build(jitdata *jd) {
 583         int32_t ds = dumpmemory_marker();
 584
 585         dominance_frontier_info *dfi = dominance_frontier_init(jd);
 586         dominance_frontier_for_block(dfi, jd->basicblocks);
 587         dominance_frontier_store(dfi);
 588 }
 589
 590 #include "vm/jit/show.h"
 591 #include "vm/jit/python.h"
 592
 593 extern void graph_add_edge( graphdata *gd, int from, int to );
 594
 595 void dominator_tree_validate(jitdata *jd, dominatordata *_dd) {
 596         int32_t ds = dumpmemory_marker();
 597         graphdata *gd;
 598         int i, j;
 599         basicblock *bptr, **it;
 600         dominatordata *dd;
 601         int *itnr;
 602         bool found;
 603
 604         fprintf(stderr, "%s/%s: \n", jd->m->class->name->text, jd->m->name->text);
 605         gd = graph_init(jd->basicblockcount);
 606
 607         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 608                 for (it = bptr->successors; it != bptr->successors + bptr->successorcount; ++it) {
 609                         graph_add_edge(gd, bptr->nr, (*it)->nr);
 610                 }
 611         }
 612
 613         dd = compute_Dominators(gd, jd->basicblockcount);
 614
 615         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 616                 if (bptr->flags >= BBREACHED) {
 617                         if (bptr->idom == NULL) {
 618                                 if (!(dd->idom[bptr->nr] == -1)) {
 619                                         printf("-- %d %d\n", dd->idom[bptr->nr], bptr->nr);
 620                                         assert(0);
 621                                 }
 622                         } else {
 623                                 assert(dd->idom[bptr->nr] == bptr->idom->nr);
 624                         }
 625                 }
 626         }
 627
 628         computeDF(gd, dd, jd->basicblockcount, 0);
 629
 630         for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
 631                 if (bptr->flags >= BBREACHED) {
 632                         assert(bptr->domfrontiercount == dd->num_DF[bptr->nr]);
 633                         for (itnr = dd->DF[bptr->nr]; itnr != dd->DF[bptr->nr] + dd->num_DF[bptr->nr]; ++itnr) {
 634                                 found = false;
 635                                 for (it = bptr->domfrontier; it != bptr->domfrontier + bptr->domfrontiercount; ++it) {
 636                                         if ((*it)->nr == *itnr) {
 637                                                 found =true; break;
 638                                         }
 639                                 }
 640                                 assert(found);
 641                         }
 642                 }
 643         }
 644
 645         dumpmemory_release(ds);
 646 }
 647
 648 /*
 649  * These are local overrides for various environment variables in Emacs.
 650  * Please do not remove this and leave it at the end of the file, where
 651  * Emacs will automagically detect them.
 652  * ---------------------------------------------------------------------
 653  * Local variables:
 654  * mode: c
 655  * indent-tabs-mode: t
 656  * c-basic-offset: 4
 657  * tab-width: 4
 658  * End:
 659  */