2
** Author(s): Kostis Sagonas
3
** Documentation added by TLS 02/02
4
** Contact: xsb-contact@cs.sunysb.edu
6
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
8
** XSB is free software; you can redistribute it and/or modify it under the
9
** terms of the GNU Library General Public License as published by the Free
10
** Software Foundation; either version 2 of the License, or (at your option)
13
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
14
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15
** FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for
18
** You should have received a copy of the GNU Library General Public License
19
** along with XSB; if not, write to the Free Software Foundation,
20
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22
** $Id: wfs_xsb_i.h,v 1.15 2005/11/16 17:32:06 dwarren Exp $
27
/* special debug includes */
28
#include "debugs/debug_delay.h"
30
/*----------------------------------------------------------------------*/
32
#define unvisit(leader) \
33
for (csf = leader; csf >= (ComplStackFrame)openreg; csf--) \
34
compl_visited(csf) = FALSE
36
/*----------------------------------------------------------------------*/
38
#define edge_alloc_chunk_size (1024 * sizeof(struct ascc_edge))
40
static char *edge_space_chunk_ptr = NULL;
42
static EPtr free_edges = NULL, free_edge_space = NULL, top_edge_space = NULL;
44
void abolish_edge_space(void)
48
while (edge_space_chunk_ptr) {
49
t = *(char **)edge_space_chunk_ptr;
50
mem_dealloc(edge_space_chunk_ptr,edge_alloc_chunk_size+sizeof(Cell),TABLE_SPACE);
51
edge_space_chunk_ptr = t;
53
free_edges = free_edge_space = top_edge_space = NULL;
56
static EPtr alloc_more_edge_space(void)
60
if ((t = (char *)mem_alloc(edge_alloc_chunk_size+sizeof(Cell),TABLE_SPACE)) == NULL)
61
xsb_abort("No space to allocate more edges for SCC detection");
62
*(char **)t = edge_space_chunk_ptr;
63
edge_space_chunk_ptr = t;
64
free_edge_space = (EPtr)(t+sizeof(Cell));
65
top_edge_space = (EPtr)(t+edge_alloc_chunk_size+sizeof(Cell));
66
return free_edge_space++;
69
#define Free_Edge(theEdge) \
70
next_edge(theEdge) = free_edges; \
73
#define New_Edge(theEdge,FromEptr,ToNode) \
75
theEdge = free_edges; \
76
free_edges = next_edge(free_edges); \
78
if (free_edge_space < top_edge_space) { \
79
theEdge = free_edge_space++; \
81
theEdge = alloc_more_edge_space(); \
84
edge_to_node(theEdge) = (ComplStackFrame) ToNode; \
85
next_edge(theEdge) = FromEptr; \
88
/* Add a dependency graph edge, and its transpose as long as the
89
parent node csf2 (DG "from" node / DGT "to" node) is not completed
90
and lies within the ASCC */
92
#define add_ascc_edges(subgoal,cs_frame,leader_cs_frame) \
93
csf2 = (ComplStackFrame)subg_compl_stack_ptr(subgoal); \
94
if (leader_cs_frame >= csf2 && !is_completed(subgoal)) { \
95
New_Edge(eptr, compl_DGT_edges(cs_frame), csf2); \
96
New_Edge(eptr, compl_DG_edges(csf2), cs_frame); \
99
static void reclaim_edge_space(ComplStackFrame csf_ptr)
103
e = compl_DG_edges(csf_ptr);
109
compl_DG_edges(csf_ptr) = NULL;
110
e = compl_DGT_edges(csf_ptr);
116
compl_DGT_edges(csf_ptr) = NULL;
119
/*----------------------------------------------------------------------*/
120
/* These macros abstract the fact that SLG-WAM and CHAT construct the */
121
/* subgoal dependency graph by looking at different data structures. */
122
/*----------------------------------------------------------------------*/
124
#define first_consumer(SUBG,CSF) (subg_asf_list_ptr(SUBG))
125
#define ptcp_of_gen(SUBG,CSF) ((VariantSF)(tcp_ptcp(subg_cp_ptr(SUBG))))
126
#define ptcp_of_cons(CONS_CP) ((VariantSF)(nlcp_ptcp(CONS_CP)))
127
#define ptcp_of_csusp(CSUSP_CP) ((VariantSF)(csf_ptcp(CSUSP_CP)))
129
/*----------------------------------------------------------------------*/
131
static inline void construct_dep_graph(CTXTdeclc ComplStackFrame leader_compl_frame)
135
VariantSF p, source_subg;
136
ComplStackFrame csf1, csf2;
138
csf1 = leader_compl_frame;
139
while (csf1 >= (ComplStackFrame)openreg) {
140
source_subg = compl_subgoal_ptr(csf1);
141
if (!is_completed(source_subg)) {
142
/*--- find the edge of the DepGraph due to the generator node ---*/
143
if ((p = ptcp_of_gen(source_subg,csf1)) != NULL) {
144
add_ascc_edges(p, csf1, leader_compl_frame);
146
/*--- find the edges of the DepGraph due to the consumers ---*/
147
for (asf = first_consumer(source_subg,csf1);
148
asf != NULL; asf = nlcp_prevlookup(asf)) {
149
if ((p = ptcp_of_cons(asf)) != NULL) {
150
add_ascc_edges(p, csf1, leader_compl_frame);
153
/*--- find the edges of the DepGraph due to the suspended nodes ---*/
154
for (nsf = subg_compl_susp_ptr(source_subg);
155
nsf != NULL; nsf = csf_prevcsf(nsf)) {
156
if ((p = ptcp_of_csusp(nsf)) != NULL) {
157
add_ascc_edges(p, csf1, leader_compl_frame);
161
csf1 = (ComplStackFrame)next_compl_frame(csf1);
163
#ifdef VERBOSE_COMPLETION
164
xsb_dbgmsg((LOG_DEBUG,"! Constructed the edges of the DepGraph"));
168
/*----------------------------------------------------------------------*/
169
/* The following function handles negation for Batched Scheduling. */
170
/*----------------------------------------------------------------------*/
172
static void batched_compute_wfs(CTXTdeclc CPtr leader_compl_frame,
174
VariantSF leader_subg)
176
CPtr ComplStkFrame; /* CopyFrame */
179
CPtr cont_breg = leader_breg;
181
/*----------------------------------------------------------------------*/
182
/* Perform a check whether exact completion is needed (sccs_needed).
183
For subgoals that are already marked as (early) completed,
184
preclude their completion suspension frames from ever being
185
secheduled and the memory occupied by their chat areas is
190
ComplStkFrame = leader_compl_frame;
191
while (ComplStkFrame >= openreg) {
192
curr_subg = compl_subgoal_ptr(ComplStkFrame);
193
if (is_completed(curr_subg)) {
194
subg_compl_susp_ptr(curr_subg) = NULL;
196
if (subg_compl_susp_ptr(curr_subg) != NULL) sccs_needed = TRUE;
198
ComplStkFrame = next_compl_frame(ComplStkFrame);
201
/**********************************************************************/
202
/* NOTE: many of the following assume that leader_compl_frame
203
* remains unchanged */
204
/*----------------------------------------------------------------------*/
205
/* The general algorithm for exact SCC check is defined in the 1998
206
SLGWAM TOPLAS paper. Below we will
208
1) Construct a dependency graph (DG) + its transpose (DGT) via
209
construct_dep_graph((ComplStackFrame)leader_compl_frame). Nodes
210
of this graph are formed via cells in compretion stack frames
211
compl_DG_edges, and compl_DGT_edges.
213
2) Traverse that dependency graph to find an independent SCC,
214
$SCC_1$ This is the combined purpose of DFS_DGT(), unvisit() and
215
find_independent_scc() (see the commentary on DFS_DGT in
216
scc_xsb.c). At the end of this process, subgoals in the
217
independent SCC have compl_visited marked as TRUE
219
3) Check the independent SCC to see whether there is a negative
220
loop --- non_lrd_stratified is TRUE if there is such a loop.
221
This is done directly in this function, for each subgoal $S$ in
222
the independent SCC, the completion_suspension frames if $S$ are
223
traversed to see whether there is a ptcp (root subgoal) pointer
224
to some subgoal $S'$ in the independet SCC. If so,
225
non_lrd_stratified is set to true, and the $S$ is marked as
233
ComplStackFrame csf, max_finish_csf;
234
xsbBool non_lrd_stratified;
236
#ifdef VERBOSE_COMPLETION
237
xsb_dbgmsg((LOG_DEBUG,"\t===> SCC detection is needed...(%d subgoals in ASCC)...",
238
(int)((leader_compl_frame-openreg)/COMPLFRAMESIZE+1)));
239
print_completion_stack();
242
construct_dep_graph(CTXTc (ComplStackFrame)leader_compl_frame);
243
dbg_print_completion_stack(LOG_COMPLETION);
245
max_finish_csf = DFS_DGT(CTXTc (ComplStackFrame)leader_compl_frame);
246
xsb_dbgmsg((LOG_COMPLETION,
247
"! MAX FINISH_SUBGOAL AT COMPL STACK: %p",max_finish_csf));
248
/* mark as not visited all subgoals in the completion stack
249
* below leader_compl_frame */
250
unvisit((ComplStackFrame)leader_compl_frame);
252
/* mark as visited all subgoals in the same SCC as max_finish_csf
253
* by traversing the SDG */
254
find_independent_scc(max_finish_csf);
256
dbg_print_completion_stack(LOG_COMPLETION);
258
/* Perform a LRD stratification check of the program-query pair */
259
/* and classify the completion suspensions as stratified or not. */
260
ComplStkFrame = leader_compl_frame;
261
non_lrd_stratified = FALSE;
263
while (ComplStkFrame >= openreg) {
265
VariantSF susp_subgoal;
267
curr_subg = compl_subgoal_ptr(ComplStkFrame);
268
if (!is_completed(curr_subg)) {
269
if (compl_visited(ComplStkFrame) != FALSE) {
270
curr_subg = compl_subgoal_ptr(ComplStkFrame);
271
for (nsf = subg_compl_susp_ptr(curr_subg);
272
nsf != NULL; nsf = csf_prevcsf(nsf)) {
273
if ((susp_subgoal = ptcp_of_csusp(nsf)) != NULL) {
274
susp_csf = subg_compl_stack_ptr(susp_subgoal);
275
if (!is_completed(susp_subgoal) &&
276
susp_csf <= leader_compl_frame &&
277
compl_visited(susp_csf) != FALSE) {
278
/*--- The suspended subgoal is in the completable SCC ---*/
279
mark_delayed(ComplStkFrame, susp_csf, nsf);
280
non_lrd_stratified = TRUE;
281
xsb_dbgmsg((LOG_DELAY, "\t Subgoal "));
282
dbg_print_subgoal(LOG_DELAY,stddbg,(VariantSF)susp_subgoal);
283
xsb_dbgmsg((LOG_DELAY, " depends negatively on subgoal "));
284
dbg_print_subgoal(LOG_DELAY, stddbg, curr_subg);
285
xsb_dbgmsg((LOG_DELAY, "\n"));
286
} /* no completed susp_subg */
290
} /* skip completed subgoals in the completion stack */
291
ComplStkFrame = next_compl_frame(ComplStkFrame);
294
/* #define SERIOUS_DEBUGGING_NEEDED */
295
#ifdef SERIOUS_DEBUGGING_NEEDED
296
print_completion_stack();
299
/*----------------------------------------------------------------------*/
301
In the case where there is no loop through negation in the
302
independent SCC (non_lrd_stratified == FALSE, then the SLGWAM
303
needs to find the continuation, the youngest subgoal of the
304
ASCC that will not be completed.
306
If the independent SCC has a loop through negation, the
307
continuation pointer will be the leader breg, otherwise, it
308
will be the breg of the youngest subgoal not in the independent
309
ASCC (I dont understand this, according to my thinking it might
310
as well be the leader, as we will have to do SCC checks, etc
313
One trick that is used is that compl_visited can now be set to
314
DELAYED (-1), FALSE (0) or true (1). The continuation will be
315
set to the breg of the first subgoal whose compl_visited value
316
is neither FALSE or delayed.
318
While I have not verified this, my understanding is that
319
starting with openreg, there will be a contiguous segment of
320
compl stack frames that are TRUE, followed by a csf that is
321
either FALSE or DELAYED. Apparently it should be DELAYED only
322
if the independent SCC contains aloop through negation.
323
Therefore, I dont see why there is a <= FALSE below --
324
according to my theory (which could be wrong) it should ==
325
FALSE, since non_lrd_stratified == FALSE.
328
if (non_lrd_stratified == FALSE) {
330
for (ComplStkFrame = openreg;
331
!found && ComplStkFrame <= leader_compl_frame;
332
ComplStkFrame = prev_compl_frame(ComplStkFrame)) {
333
if (compl_visited(ComplStkFrame) <= FALSE) {
334
cont_breg = subg_cp_ptr(compl_subgoal_ptr(ComplStkFrame));
336
xsb_dbgmsg((LOG_COMPLETION,
337
"------ Setting TBreg to %p...", cont_breg));
341
if (!found) { /* case in which the ASCC contains only one SCC */
342
/* and all subgoals will be completed (no delay) */
343
cont_breg = tcp_prevbreg(leader_breg);
345
} else { /* the chosen SCC has a loop through negation */
346
for (ComplStkFrame = openreg; ComplStkFrame <= leader_compl_frame;
347
ComplStkFrame = prev_compl_frame(ComplStkFrame)) {
348
if (compl_visited(ComplStkFrame) != FALSE)
349
compl_visited(ComplStkFrame) = DELAYED;
351
cont_breg = subg_cp_ptr(compl_subgoal_ptr(leader_compl_frame));
353
xsb_dbgmsg((LOG_COMPLETION, "------ Setting TBreg to %p...", cont_breg));
356
/*----------------------------------------------------------------------*/
358
The next loop has two functions. First, any subgoals that are
359
completely evaluated (those that are visited but not delayed)
360
are marked as completed. In addition, breg will be set to
361
point to the cP for the the youngest subgoal that has been
362
visited (delayed or not). The failure continuation of this CP
363
in turn will be the continuation obtained above.
365
One point to make is that reclaim_incomplete_table_structs()
366
Clears up some table structures for subsumptive tabling, and
367
presumably the answer list for variant tabling. It also frees
368
consumer choice points in CHAT. In either case, frozen local
369
stack, heap, (and trail & cp space in the SLGWAM) will only be
370
reclaimed upon completion of the leader.
374
for (ComplStkFrame = leader_compl_frame; ComplStkFrame >= openreg;
375
ComplStkFrame = next_compl_frame(ComplStkFrame)) {
376
if (compl_visited(ComplStkFrame) != FALSE) {
377
curr_subg = compl_subgoal_ptr(ComplStkFrame);
378
if (compl_visited(ComplStkFrame) != DELAYED) {
380
if( !is_completed(curr_subg) )
382
mark_as_completed(curr_subg);
383
WakeDependentThreads(th, curr_subg);
386
mark_as_completed(curr_subg);
388
reclaim_incomplete_table_structs(curr_subg);
389
if (neg_simplif_possible(curr_subg)) {
390
simplify_neg_fails(CTXTc curr_subg);
394
/*----------------------------------------------------------------------*/
395
/* Now, its time to schedule the completion suspensions found
396
for the youngest subgoal in the independent SCC, as found in
399
There are a couple of anomalies in this procedure, for the
400
SLGWAM. The first is that we have completion suspension as
401
"single-dispatch", that is only one completion suspension is
402
scheduled for each dependency check --- I thought that we
403
used to dispatch completion_suspension frames for all
404
subgoals in the independent SCC??? Second, there is a
405
completion_suspension CP that is created.
406
Completion_suspension CPs, as opposed to completion
407
suspension frames, are archaic remnants of single-stack
408
scheduling. I believe their creation here is unnecessary.
409
In principle, we should be able to simply set the breg to
410
the first of the completion_suspension Frames.
413
if ((nsf = subg_compl_susp_ptr(curr_subg)) != NULL) {
416
set_min(min_breg, breg, bfreg);
417
if (compl_visited(ComplStkFrame) != DELAYED) {
418
save_compl_susp_cp(min_breg, cont_breg, nsf);
420
/*-- forget these completion suspensions --*/
421
subg_compl_susp_ptr(curr_subg) = NULL;
422
#ifdef VERBOSE_COMPLETION
423
xsb_dbgmsg((LOG_DEBUG,"------ Setting Breg to %p...", breg));
425
} else { /* unsuspend only those suspensions that are delayed */
426
CPtr dnsf = NULL, ndnsf = NULL;
427
CPtr head_dnsf = NULL, head_ndnsf = NULL;
428
while (nsf != NULL) { /* partition into two lists */
429
if (csf_neg_loop(nsf) == FALSE) {
430
if (ndnsf == NULL) head_ndnsf = nsf;
431
else csf_prevcsf(ndnsf) = nsf;
433
nsf = csf_prevcsf(nsf);
434
csf_prevcsf(ndnsf) = NULL;
436
if (dnsf == NULL) head_dnsf = nsf;
437
else csf_prevcsf(dnsf) = nsf;
439
nsf = csf_prevcsf(nsf);
440
csf_prevcsf(dnsf) = NULL;
443
if (head_dnsf != NULL) {
444
save_compl_susp_cp(min_breg, cont_breg, head_dnsf);
447
subg_compl_susp_ptr(curr_subg) = head_ndnsf;
449
cont_breg = breg; /* So that other Compl_Susp_CPs can be saved. */
454
xsb_dbgmsg((LOG_COMPLETION, "------ Completed the chosen SCC..."));
455
/*----------------------------------------------------------------------*/
456
/* Finally, compact the Completion Stack (and reclaim edge
457
space for the dependency graphs).
459
Might be useful to only copy the frame if CopyFrame is not
463
ComplStkFrame = CopyFrame = leader_compl_frame;
464
while (ComplStkFrame >= openreg) {
465
curr_subg = compl_subgoal_ptr(ComplStkFrame);
466
reclaim_edge_space((ComplStackFrame)ComplStkFrame);
467
if (!is_completed(curr_subg)) {
468
subg_compl_stack_ptr(curr_subg) = CopyFrame;
469
/* the macro below also updates CopyFrame */
470
compact_completion_frame(CopyFrame, ComplStkFrame, curr_subg);
471
} else { /* this may be done 2x! */
472
reclaim_incomplete_table_structs(curr_subg);
474
ComplStkFrame = next_compl_frame(ComplStkFrame);
476
openreg = prev_compl_frame(CopyFrame);
478
/*----------------------------------------------------------------------*/
481
This next loop chains some of the TCPs, but does not form what
482
I would think of as a scheduling chain -- it simply removes any
483
pointers to completed subgoals whose space has been reclaimed.
487
tcp_prevbreg(subg_cp_ptr(compl_subgoal_ptr(leader_compl_frame))) =
488
tcp_prevbreg(subg_cp_ptr(leader_subg));
490
looks anomalous at first, but the leader compl_frame may have
491
been compacted away, thus its continuation must be preserved for
492
whoever is the new leader.
494
However, I dont believe that the "for" loop is necessary, as it
495
doesn't matter what the tcp_breg is for choice points that are
496
not leaders (and if they are promoted to leaders, their
497
tcp_prevbreg value will be adjusted anyway.
500
tcp_prevbreg(subg_cp_ptr(compl_subgoal_ptr(leader_compl_frame))) =
501
tcp_prevbreg(subg_cp_ptr(leader_subg));
502
for (ComplStkFrame = next_compl_frame(leader_compl_frame);
503
ComplStkFrame >= openreg;
504
ComplStkFrame = next_compl_frame(ComplStkFrame)){
505
tcp_prevbreg(subg_cp_ptr(compl_subgoal_ptr(ComplStkFrame))) =
506
subg_cp_ptr(compl_subgoal_ptr(prev_compl_frame(ComplStkFrame)));
508
} /* if sccs_needed */
509
else { /* sccs not needed */
510
ComplStkFrame = leader_compl_frame;
511
while (ComplStkFrame >= openreg) {
512
curr_subg = compl_subgoal_ptr(ComplStkFrame);
514
if( !is_completed(curr_subg) )
516
mark_as_completed(curr_subg);
517
WakeDependentThreads(th, curr_subg);
520
mark_as_completed(curr_subg);
522
if (neg_simplif_possible(curr_subg)) {
523
simplify_neg_fails(CTXTc curr_subg);
525
ComplStkFrame = next_compl_frame(ComplStkFrame);
528
ComplStkFrame = leader_compl_frame;
529
while (ComplStkFrame >= openreg) {
530
curr_subg = compl_subgoal_ptr(ComplStkFrame);
531
reclaim_incomplete_table_structs(curr_subg);
532
ComplStkFrame = next_compl_frame(ComplStkFrame);
534
/* point openreg to first empty space */
535
openreg = prev_compl_frame(leader_compl_frame);
538
xsb_dbgmsg((LOG_COMPLETION, "------ Completed an ASCC..."));
539
} /* compute_wfs() */
541
/*----------------------------------------------------------------------*/
added
removed
emu/wfs_xsb_i.h
