YAP 7.1.0
tab.completion.c
1/************************************************************************
2** **
3** The YapTab/YapOr/OPTYap systems **
4** **
5** YapTab extends the Yap Prolog engine to support sequential tabling **
6** YapOr extends the Yap Prolog engine to support or-parallelism **
7** OPTYap extends the Yap Prolog engine to support or-parallel tabling **
8** **
9** **
10** Yap Prolog was developed at University of Porto, Portugal **
11** **
12************************************************************************/
13
14/***********************
15** Includes **
16***********************/
17
18#include "Yap.h"
19#ifdef TABLING
20#include "Yatom.h"
21#include "YapHeap.h"
22#include "tab.macros.h"
23#ifdef YAPOR
24#include "or.macros.h"
25#endif /* YAPOR */
26
27
28
29/******************************
30** Local functions **
31******************************/
32
33#ifdef YAPOR
34static void complete_suspension_branch(susp_fr_ptr susp_fr, choiceptr top_cp, or_fr_ptr *chain_or_fr, dep_fr_ptr *chain_dep_fr) {
35 or_fr_ptr aux_or_fr;
36 sg_fr_ptr aux_sg_fr;
37 dep_fr_ptr aux_dep_fr;
38
39 /* complete all subgoals */
40 aux_dep_fr = SuspFr_top_dep_fr(susp_fr);
41 aux_sg_fr = SuspFr_top_sg_fr(susp_fr);
42 if (DepFr_leader_dep_is_on_stack(aux_dep_fr)) {
43 while (aux_sg_fr &&
44 /* continue if the subgoal was early completed */
45 /* SgFr_state(aux_sg_fr) == evaluating && */
46 (SgFr_state(aux_sg_fr) == evaluating || SgFr_first_answer(aux_sg_fr) == SgFr_answer_trie(aux_sg_fr)) &&
47 EQUAL_OR_YOUNGER_CP(SgFr_gen_cp(aux_sg_fr), top_cp)) {
48 mark_as_completed(aux_sg_fr);
49 aux_sg_fr = SgFr_next(aux_sg_fr);
50 }
51 } else {
52 while (aux_sg_fr &&
53 /* continue if the subgoal was early completed */
54 /* SgFr_state(aux_sg_fr) == evaluating && */
55 (SgFr_state(aux_sg_fr) == evaluating || SgFr_first_answer(aux_sg_fr) == SgFr_answer_trie(aux_sg_fr)) &&
56 YOUNGER_CP(SgFr_gen_cp(aux_sg_fr), top_cp)) {
57 mark_as_completed(aux_sg_fr);
58 aux_sg_fr = SgFr_next(aux_sg_fr);
59 }
60 }
61
62 /* chain dependency frames to release (using DepFr_next) */
63 while (IS_UNLOCKED_DEP_FR(aux_dep_fr) &&
64 YOUNGER_CP(DepFr_cons_cp(aux_dep_fr), top_cp)) {
65 dep_fr_ptr next_dep_fr;
66 LOCK_DEP_FR(aux_dep_fr);
67 next_dep_fr = DepFr_next(aux_dep_fr);
68 DepFr_next(aux_dep_fr) = *chain_dep_fr;
69 *chain_dep_fr = aux_dep_fr;
70 aux_dep_fr = next_dep_fr;
71 }
72
73 /* chain or-frames to release (using OrFr_next_on_stack) **
74 ** we use the OrFr_next_on_stack field instead of OrFr_next **
75 ** to avoid conflicts with the 'find_dependency_node' macro */
76 aux_or_fr = SuspFr_top_or_fr_on_stack(susp_fr);
77 while (IS_UNLOCKED(OrFr_lock(aux_or_fr))) {
78 susp_fr_ptr aux_susp_fr;
79 or_fr_ptr next_or_fr_on_stack;
80 OPTYAP_ERROR_CHECKING(complete_suspension_branch, YOUNGER_CP(top_cp, GetOrFr_node(aux_or_fr)));
81 LOCK_OR_FRAME(aux_or_fr);
82 aux_susp_fr = OrFr_suspensions(aux_or_fr);
83 while (aux_susp_fr) {
84 susp_fr_ptr next_susp_fr;
85 complete_suspension_branch(aux_susp_fr, GetOrFr_node(aux_or_fr), chain_or_fr, chain_dep_fr);
86 next_susp_fr = SuspFr_next(aux_susp_fr);
87 FREE_SUSPENSION_FRAME(aux_susp_fr);
88 aux_susp_fr = next_susp_fr;
89 }
90 next_or_fr_on_stack = OrFr_next_on_stack(aux_or_fr);
91 OrFr_next_on_stack(aux_or_fr) = *chain_or_fr;
92 *chain_or_fr = aux_or_fr;
93 aux_or_fr = next_or_fr_on_stack;
94 }
95
96 return;
97}
98#endif /* YAPOR */
99
100
101
102/*******************************
103** Global functions **
104*******************************/
105
106void private_completion(sg_fr_ptr sg_fr) {
107 CACHE_REGS
108
109 /* complete subgoals */
110#ifdef LIMIT_TABLING
111 sg_fr_ptr aux_sg_fr;
112 while (LOCAL_top_sg_fr != sg_fr) {
113 aux_sg_fr = LOCAL_top_sg_fr;
114 LOCAL_top_sg_fr = SgFr_next(aux_sg_fr);
115 mark_as_completed(aux_sg_fr);
116 insert_into_global_sg_fr_list(aux_sg_fr);
117 }
118 aux_sg_fr = LOCAL_top_sg_fr;
119 LOCAL_top_sg_fr = SgFr_next(aux_sg_fr);
120 mark_as_completed(aux_sg_fr);
121 insert_into_global_sg_fr_list(aux_sg_fr);
122#else
123 while (LOCAL_top_sg_fr != sg_fr) {
124 mark_as_completed(LOCAL_top_sg_fr);
125 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
126 }
127 mark_as_completed(LOCAL_top_sg_fr);
128 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
129#endif /* LIMIT_TABLING */
130
131 /* release dependency frames */
132 while (EQUAL_OR_YOUNGER_CP(DepFr_cons_cp(LOCAL_top_dep_fr), B)) { /* never equal if batched scheduling */
133 dep_fr_ptr dep_fr = DepFr_next(LOCAL_top_dep_fr);
134 FREE_DEPENDENCY_FRAME(LOCAL_top_dep_fr);
135 LOCAL_top_dep_fr = dep_fr;
136 }
137
138 /* adjust freeze registers */
139 adjust_freeze_registers();
140
141 /* adjust thread dependency */
142#ifdef THREADS_CONSUMER_SHARING
143 ThDepFr_state(GLOBAL_th_dep_fr(worker_id)) = working;
144 ThDepFr_next(GLOBAL_th_dep_fr(worker_id)) = worker_id;
145#endif /* THREADS_CONSUMER_SHARING */
146 return;
147}
148
149
150#ifdef YAPOR
151void public_completion(void) {
152 CACHE_REGS
153 dep_fr_ptr chain_dep_fr, next_dep_fr;
154 or_fr_ptr chain_or_fr, top_or_fr, next_or_fr;
155 susp_fr_ptr susp_fr, next_susp_fr;
156 qg_sol_fr_ptr solutions, aux_solutions;
157
158 if (YOUNGER_CP(Get_LOCAL_top_cp(), B_FZ)) {
159 /* the current node is a generator node without younger consumer **
160 ** nodes --> we only have the current node to complete */
161 sg_fr_ptr top_sg_fr;
162
163 /* complete subgoals */
164#ifdef DETERMINISTIC_TABLING
165 if (IS_DET_GEN_CP(Get_LOCAL_top_cp()))
166 top_sg_fr = SgFr_next(DET_GEN_CP(Get_LOCAL_top_cp())->cp_sg_fr);
167 else
168#endif /* DETERMINISTIC_TABLING */
169 top_sg_fr = SgFr_next(GEN_CP(Get_LOCAL_top_cp())->cp_sg_fr);
170 do {
171 mark_as_completed(LOCAL_top_sg_fr);
172 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
173 } while (LOCAL_top_sg_fr != top_sg_fr);
174
175 /* no dependency frames to release */
176 chain_dep_fr = NULL;
177
178 /* no need to adjust freeze registers */
179 } else {
180 /* the current node is a leader node with younger consumer **
181 ** nodes ---> we need to complete all dependent subgoals */
182
183 /* complete subgoals */
184 if (DepFr_leader_dep_is_on_stack(LOCAL_top_dep_fr)) {
185 while (LOCAL_top_sg_fr &&
186 EQUAL_OR_YOUNGER_CP(SgFr_gen_cp(LOCAL_top_sg_fr), Get_LOCAL_top_cp())) {
187 mark_as_completed(LOCAL_top_sg_fr);
188 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
189 }
190 } else {
191 while (LOCAL_top_sg_fr &&
192 YOUNGER_CP(SgFr_gen_cp(LOCAL_top_sg_fr), Get_LOCAL_top_cp())) {
193 mark_as_completed(LOCAL_top_sg_fr);
194 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
195 }
196 }
197
198 /* chain dependency frames to release */
199 chain_dep_fr = NULL;
200 while (YOUNGER_CP(DepFr_cons_cp(LOCAL_top_dep_fr), Get_LOCAL_top_cp())) {
201 LOCK_DEP_FR(LOCAL_top_dep_fr);
202 next_dep_fr = DepFr_next(LOCAL_top_dep_fr);
203 DepFr_next(LOCAL_top_dep_fr) = chain_dep_fr;
204 chain_dep_fr = LOCAL_top_dep_fr;
205 LOCAL_top_dep_fr = next_dep_fr;
206 }
207
208 /* adjust freeze registers */
209 adjust_freeze_registers();
210 }
211
212 /* chain or-frames to release */
213 chain_or_fr = NULL;
214 top_or_fr = Get_LOCAL_top_cp_on_stack()->cp_or_fr;
215 while (top_or_fr != LOCAL_top_or_fr) {
216 or_fr_ptr next_or_fr_on_stack;
217 LOCK_OR_FRAME(top_or_fr);
218 susp_fr = OrFr_suspensions(top_or_fr);
219 while (susp_fr) {
220 complete_suspension_branch(susp_fr, GetOrFr_node(top_or_fr), &chain_or_fr, &chain_dep_fr);
221 next_susp_fr = SuspFr_next(susp_fr);
222 FREE_SUSPENSION_FRAME(susp_fr);
223 susp_fr = next_susp_fr;
224 }
225 next_or_fr_on_stack = OrFr_next_on_stack(top_or_fr);
226 OrFr_next_on_stack(top_or_fr) = chain_or_fr;
227 chain_or_fr = top_or_fr;
228 top_or_fr = next_or_fr_on_stack;
229 }
230 LOCK_OR_FRAME(top_or_fr);
231 susp_fr = OrFr_suspensions(top_or_fr);
232 while (susp_fr) {
233 complete_suspension_branch(susp_fr, GetOrFr_node(top_or_fr), &chain_or_fr, &chain_dep_fr);
234 next_susp_fr = SuspFr_next(susp_fr);
235 FREE_SUSPENSION_FRAME(susp_fr);
236 susp_fr = next_susp_fr;
237 }
238 OrFr_suspensions(top_or_fr) = NULL;
239 OrFr_nearest_suspnode(top_or_fr) = top_or_fr;
240 UNLOCK_OR_FRAME(top_or_fr);
241
242 /* release dependency frames */
243 while (chain_dep_fr) {
244 next_dep_fr = DepFr_next(chain_dep_fr);
245 FREE_DEPENDENCY_FRAME(chain_dep_fr);
246 chain_dep_fr = next_dep_fr;
247 }
248
249 /* release or frames */
250 solutions = NULL;
251 while (chain_or_fr) {
252 aux_solutions = OrFr_qg_solutions(chain_or_fr);
253 if (aux_solutions) {
254 CUT_join_answers_in_an_unique_frame(aux_solutions);
255 SolFr_next(aux_solutions) = solutions;
256 solutions = aux_solutions;
257 }
258 next_or_fr = OrFr_next_on_stack(chain_or_fr);
259 FREE_OR_FRAME(chain_or_fr);
260 chain_or_fr = next_or_fr;
261 }
262 if (solutions) {
263 CUT_join_answers_in_an_unique_frame(solutions);
264 SolFr_next(solutions) = OrFr_qg_solutions(LOCAL_top_or_fr);
265 OrFr_qg_solutions(LOCAL_top_or_fr) = solutions;
266 }
267
268 /* adjust top register */
269 Set_LOCAL_top_cp_on_stack( Get_LOCAL_top_cp() );
270
271 return;
272}
273
274
275void complete_suspension_frames(or_fr_ptr or_fr) {
276 CACHE_REGS
277 dep_fr_ptr chain_dep_fr;
278 or_fr_ptr chain_or_fr;
279 susp_fr_ptr susp_fr;
280 qg_sol_fr_ptr solutions;
281
282 /* complete suspension frames */
283 chain_dep_fr = NULL;
284 chain_or_fr = NULL;
285 susp_fr = OrFr_suspensions(or_fr);
286 do {
287 susp_fr_ptr next_susp_fr;
288 complete_suspension_branch(susp_fr, GetOrFr_node(or_fr), &chain_or_fr, &chain_dep_fr);
289 next_susp_fr = SuspFr_next(susp_fr);
290 FREE_SUSPENSION_FRAME(susp_fr);
291 susp_fr = next_susp_fr;
292 } while (susp_fr);
293 OrFr_suspensions(or_fr) = NULL;
294 OrFr_nearest_suspnode(or_fr) = or_fr;
295
296 /* release dependency frames */
297 while (chain_dep_fr) {
298 dep_fr_ptr next_dep_fr;
299 next_dep_fr = DepFr_next(chain_dep_fr);
300 FREE_DEPENDENCY_FRAME(chain_dep_fr);
301 chain_dep_fr = next_dep_fr;
302 }
303
304 /* release or frames */
305 solutions = NULL;
306 while (chain_or_fr) {
307 or_fr_ptr next_or_fr;
308 qg_sol_fr_ptr aux_solutions;
309 aux_solutions = OrFr_qg_solutions(chain_or_fr);
310 if (aux_solutions) {
311 CUT_join_answers_in_an_unique_frame(aux_solutions);
312 SolFr_next(aux_solutions) = solutions;
313 solutions = aux_solutions;
314 }
315 next_or_fr = OrFr_next_on_stack(chain_or_fr);
316 FREE_OR_FRAME(chain_or_fr);
317 chain_or_fr = next_or_fr;
318 }
319 if (solutions) {
320 CUT_join_answers_in_an_unique_frame(solutions);
321 SolFr_next(solutions) = OrFr_qg_solutions(or_fr);
322 OrFr_qg_solutions(LOCAL_top_or_fr) = solutions;
323 }
324
325 return;
326}
327
328
329void suspend_branch(void) {
330 CACHE_REGS
331 or_fr_ptr or_frame;
332
333 /* suspension only occurs in shared nodes that **
334 ** are leaders with younger consumer nodes */
335#ifdef DEBUG_OPTYAP
336 OPTYAP_ERROR_CHECKING(suspend_branch, Get_LOCAL_top_cp()->cp_or_fr != LOCAL_top_or_fr);
337 OPTYAP_ERROR_CHECKING(suspend_branch, B_FZ == Get_LOCAL_top_cp());
338 OPTYAP_ERROR_CHECKING(suspend_branch, YOUNGER_CP(Get_LOCAL_top_cp(), Get_LOCAL_top_cp_on_stack()));
339 OPTYAP_ERROR_CHECKING(suspend_branch, Get_LOCAL_top_cp()->cp_or_fr != LOCAL_top_or_fr);
340 or_frame = Get_LOCAL_top_cp_on_stack()->cp_or_fr;
341 while (or_frame != LOCAL_top_or_fr) {
342 OPTYAP_ERROR_CHECKING(suspend_branch, YOUNGER_CP(Get_LOCAL_top_cp(), GetOrFr_node(or_frame)));
343 or_frame = OrFr_next_on_stack(or_frame);
344 }
345#endif /* DEBUG_OPTYAP */
346
347 or_frame = Get_LOCAL_top_cp_on_stack()->cp_or_fr;
348 LOCK_OR_FRAME(or_frame);
349 if (B_FZ == Get_LOCAL_top_cp_on_stack() && OrFr_owners(or_frame) > 1) {
350 /* there are other workers sharing the whole branch **
351 ** --> we can avoid suspension <-- */
352
353 /* update shared nodes */
354 OrFr_owners(or_frame)--;
355 UNLOCK_OR_FRAME(or_frame);
356 or_frame = OrFr_next_on_stack(or_frame);
357 while (or_frame != LOCAL_top_or_fr) {
358 LOCK_OR_FRAME(or_frame);
359 OrFr_owners(or_frame)--;
360 UNLOCK_OR_FRAME(or_frame);
361 or_frame = OrFr_next_on_stack(or_frame);
362 }
363 } else {
364 /* the branch has private parts **
365 ** --> suspend branch <-- */
366 susp_fr_ptr new_susp_fr;
367 long h_size, b_size, tr_size;
368 UNLOCK_OR_FRAME(or_frame);
369
370 /* alloc suspension frame */
371 h_size = (unsigned long) H_FZ - (unsigned long) Get_LOCAL_top_cp()->cp_h;
372 b_size = (unsigned long) Get_LOCAL_top_cp() - (unsigned long) B_FZ;
373 tr_size = (unsigned long) TR_FZ - (unsigned long) Get_LOCAL_top_cp()->cp_tr;
374 new_suspension_frame(new_susp_fr, Get_LOCAL_top_cp_on_stack()->cp_or_fr, LOCAL_top_dep_fr, LOCAL_top_sg_fr,
375 Get_LOCAL_top_cp()->cp_h, B_FZ, Get_LOCAL_top_cp()->cp_tr, h_size, b_size, tr_size);
376
377 /* store suspension frame in current top or-frame */
378 LOCK_OR_FRAME(LOCAL_top_or_fr);
379 if (OrFr_nearest_suspnode(LOCAL_top_or_fr) == LOCAL_top_or_fr)
380 OrFr_nearest_suspnode(LOCAL_top_or_fr) = NULL;
381 SuspFr_next(new_susp_fr) = OrFr_suspensions(LOCAL_top_or_fr);
382 OrFr_suspensions(LOCAL_top_or_fr) = new_susp_fr;
383 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
384 }
385
386 /* adjust top pointers */
387 while (LOCAL_top_sg_fr && YOUNGER_CP(SgFr_gen_cp(LOCAL_top_sg_fr), Get_LOCAL_top_cp_on_stack())) {
388 SgFr_gen_worker(LOCAL_top_sg_fr) = MAX_WORKERS;
389 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
390 }
391 while (LOCAL_top_sg_fr && YOUNGER_CP(SgFr_gen_cp(LOCAL_top_sg_fr), Get_LOCAL_top_cp())) {
392 LOCAL_top_sg_fr = SgFr_next(LOCAL_top_sg_fr);
393 }
394 while (YOUNGER_CP(DepFr_cons_cp(LOCAL_top_dep_fr), Get_LOCAL_top_cp())) {
395 LOCAL_top_dep_fr = DepFr_next(LOCAL_top_dep_fr);
396 }
397 Set_LOCAL_top_cp_on_stack( Get_LOCAL_top_cp() );
398
399 /* adjust freeze registers */
400 adjust_freeze_registers();
401
402 return;
403}
404
405
406void resume_suspension_frame(susp_fr_ptr resume_fr, or_fr_ptr top_or_fr) {
407 CACHE_REGS
408 or_fr_ptr or_frame;
409 sg_fr_ptr sg_frame;
410
411 /* copy suspended stacks */
412 memcpy(SuspFr_global_reg(resume_fr),
413 SuspFr_global_start(resume_fr),
414 SuspFr_global_size(resume_fr));
415 memcpy(SuspFr_local_reg(resume_fr),
416 SuspFr_local_start(resume_fr),
417 SuspFr_local_size(resume_fr));
418 memcpy(SuspFr_trail_reg(resume_fr),
419 SuspFr_trail_start(resume_fr),
420 SuspFr_trail_size(resume_fr));
421
422 OPTYAP_ERROR_CHECKING(resume_suspension_frame, DepFr_cons_cp(SuspFr_top_dep_fr(resume_fr))->cp_h != SuspFr_global_reg(resume_fr) + SuspFr_global_size(resume_fr));
423 OPTYAP_ERROR_CHECKING(resume_suspension_frame, DepFr_cons_cp(SuspFr_top_dep_fr(resume_fr))->cp_tr != SuspFr_trail_reg(resume_fr) + SuspFr_trail_size(resume_fr));
424 OPTYAP_ERROR_CHECKING(resume_suspension_frame, DepFr_cons_cp(SuspFr_top_dep_fr(resume_fr)) != SuspFr_local_reg(resume_fr));
425 OPTYAP_ERROR_CHECKING(resume_suspension_frame, (void *)Get_LOCAL_top_cp() < SuspFr_local_reg(resume_fr) + SuspFr_local_size(resume_fr));
426
427 /* update shared nodes */
428 or_frame = top_or_fr;
429 while (or_frame != LOCAL_top_or_fr) {
430 LOCK_OR_FRAME(or_frame);
431 OrFr_owners(or_frame)++;
432 UNLOCK_OR_FRAME(or_frame);
433 or_frame = OrFr_next_on_stack(or_frame);
434 }
435 or_frame = top_or_fr;
436 while (or_frame != LOCAL_top_or_fr) {
437 LOCK_OR_FRAME(or_frame);
438 BITMAP_insert(OrFr_members(or_frame), worker_id);
439 BRANCH(worker_id, OrFr_depth(or_frame)) = 1;
440 UNLOCK_OR_FRAME(or_frame);
441 or_frame = OrFr_next(or_frame);
442 }
443
444 /* adjust top pointers */
445 LOCAL_top_or_fr = top_or_fr;
446 SetOrFr_node(top_or_fr, Get_LOCAL_top_cp());
447 LOCAL_top_sg_fr = SuspFr_top_sg_fr(resume_fr);
448 LOCAL_top_dep_fr = SuspFr_top_dep_fr(resume_fr);
449 Set_LOCAL_top_cp_on_stack( GetOrFr_node(SuspFr_top_or_fr_on_stack(resume_fr)) );
450 sg_frame = LOCAL_top_sg_fr;
451 while (sg_frame && YOUNGER_CP(SgFr_gen_cp(sg_frame), Get_LOCAL_top_cp_on_stack())) {
452 SgFr_gen_worker(sg_frame) = worker_id;
453 sg_frame = SgFr_next(sg_frame);
454 }
455
456 /* adjust freeze registers */
457 adjust_freeze_registers();
458
459 /* free suspension frame */
460 FREE_SUSPENSION_FRAME(resume_fr);
461
462 return;
463}
464#endif /* YAPOR */
465#endif /* TABLING */
Yap.h
Main definitions.
or_frame
Definition: or.structs.h:61
query_goal_solution_frame
Definition: or.structs.h:135
dependency_frame
Definition: tab.structs.h:381
subgoal_frame
Definition: tab.structs.h:296