198cd349002656f07396df885d92b463cb3d14bd
[blender-staging.git] / source / blender / depsgraph / intern / eval / deg_eval.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2013 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/depsgraph_eval.cc
28  *  \ingroup depsgraph
29  *
30  * Evaluation engine entrypoints for Depsgraph Engine.
31  */
32
33 #include "intern/eval/deg_eval.h"
34
35 #include "PIL_time.h"
36
37 extern "C" {
38 #include "BLI_utildefines.h"
39 #include "BLI_task.h"
40 #include "BLI_ghash.h"
41
42 #include "BKE_depsgraph.h"
43 #include "BKE_global.h"
44
45 #include "DEG_depsgraph.h"
46 } /* extern "C" */
47
48 #include "atomic_ops.h"
49
50 #include "intern/eval/deg_eval_debug.h"
51 #include "intern/eval/deg_eval_flush.h"
52 #include "intern/nodes/deg_node.h"
53 #include "intern/nodes/deg_node_component.h"
54 #include "intern/nodes/deg_node_operation.h"
55 #include "intern/depsgraph.h"
56 #include "util/deg_util_foreach.h"
57
58 /* Unfinished and unused, and takes quite some pre-processing time. */
59 #undef USE_EVAL_PRIORITY
60
61 /* Use integrated debugger to keep track how much each of the nodes was
62  * evaluating.
63  */
64 #undef USE_DEBUGGER
65
66 namespace DEG {
67
68 /* ********************** */
69 /* Evaluation Entrypoints */
70
71 /* Forward declarations. */
72 static void schedule_children(TaskPool *pool,
73                               Depsgraph *graph,
74                               OperationDepsNode *node,
75                               const int layers,
76                               const int thread_id);
77
78 struct DepsgraphEvalState {
79         EvaluationContext *eval_ctx;
80         Depsgraph *graph;
81         int layers;
82 };
83
84 static void deg_task_run_func(TaskPool *pool,
85                               void *taskdata,
86                               int thread_id)
87 {
88         DepsgraphEvalState *state =
89                 reinterpret_cast<DepsgraphEvalState *>(BLI_task_pool_userdata(pool));
90         OperationDepsNode *node = reinterpret_cast<OperationDepsNode *>(taskdata);
91
92         BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled");
93
94         /* Should only be the case for NOOPs, which never get to this point. */
95         BLI_assert(node->evaluate);
96
97         while (true) {
98                 /* Get context. */
99                 /* TODO: Who initialises this? "Init" operations aren't able to
100                  * initialise it!!!
101                  */
102                 /* TODO(sergey): We don't use component contexts at this moment. */
103                 /* ComponentDepsNode *comp = node->owner; */
104                 BLI_assert(node->owner != NULL);
105
106                 /* Since we're not leaving the thread for until the graph branches it is
107                  * possible to have NO-OP on the way. for which evaluate() will be NULL.
108                  * but that's all fine, we'll just scheduler it's children.
109                  */
110                 if (node->evaluate) {
111                         /* Take note of current time. */
112 #ifdef USE_DEBUGGER
113                         double start_time = PIL_check_seconds_timer();
114                         DepsgraphDebug::task_started(state->graph, node);
115 #endif
116
117                         /* Perform operation. */
118                         node->evaluate(state->eval_ctx);
119
120                         /* Note how long this took. */
121 #ifdef USE_DEBUGGER
122                         double end_time = PIL_check_seconds_timer();
123                         DepsgraphDebug::task_completed(state->graph,
124                                                        node,
125                                                        end_time - start_time);
126 #endif
127                 }
128
129                 /* If there's only one outgoing link we try to immediately switch to
130                  * that node evaluation, without leaving the thread.
131                  *
132                  * It's only doable if the child don't have extra relations or all they
133                  * are satisfied.
134                  *
135                  * TODO(sergey): Checks here can be de-duplicated with the ones from
136                  * schedule_node(), however, how to do it nicely?
137                  */
138                 if (node->outlinks.size() == 1) {
139                         DepsRelation *rel = node->outlinks[0];
140                         OperationDepsNode *child = (OperationDepsNode *)rel->to;
141                         BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
142                         if (!child->scheduled) {
143                                 int id_layers = child->owner->owner->layers;
144                                 if (!((child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 &&
145                                       (id_layers & state->layers) != 0))
146                                 {
147                                         /* Node does not need an update, so can;t continue with the
148                                          * chain and need to switch to another one by leaving the
149                                          * thread.
150                                          */
151                                         break;
152                                 }
153                                 if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
154                                         BLI_assert(child->num_links_pending > 0);
155                                         atomic_sub_uint32(&child->num_links_pending, 1);
156                                 }
157                                 if (child->num_links_pending == 0) {
158                                         bool is_scheduled = atomic_fetch_and_or_uint8(
159                                                 (uint8_t *)&child->scheduled, (uint8_t)true);
160                                         if (!is_scheduled) {
161                                                 /* Node was not scheduled, switch to it! */
162                                                 node = child;
163                                         }
164                                         else {
165                                                 /* Someone else scheduled the node, leaving us
166                                                  * unemployed in this thread, we're leaving.
167                                                  */
168                                                 break;
169                                         }
170                                 }
171                                 else {
172                                         /* There are other dependencies on the child, can't do
173                                          * anything in the current thread.
174                                          */
175                                         break;
176                                 }
177                         }
178                         else {
179                                 /* Happens when having cyclic dependencies.
180                                  *
181                                  * Nothing to do here, single child was already scheduled, we
182                                  * can leave the thread now.
183                                  */
184                                 break;
185                         }
186                 }
187                 else {
188                         /* TODO(sergey): It's possible to use one of the outgoing relations
189                          * as a chain which we'll try to keep alive, but it's a bit more
190                          * involved change.
191                          */
192                         schedule_children(pool, state->graph, node, state->layers, thread_id);
193                         break;
194                 }
195         }
196 }
197
198 typedef struct CalculatePengindData {
199         Depsgraph *graph;
200         int layers;
201 } CalculatePengindData;
202
203 static void calculate_pending_func(void *data_v, int i)
204 {
205         CalculatePengindData *data = (CalculatePengindData *)data_v;
206         Depsgraph *graph = data->graph;
207         int layers = data->layers;
208         OperationDepsNode *node = graph->operations[i];
209         IDDepsNode *id_node = node->owner->owner;
210
211         node->num_links_pending = 0;
212         node->scheduled = false;
213
214         /* count number of inputs that need updates */
215         if ((id_node->layers & layers) != 0 &&
216             (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
217         {
218                 foreach (DepsRelation *rel, node->inlinks) {
219                         if (rel->from->type == DEPSNODE_TYPE_OPERATION &&
220                             (rel->flag & DEPSREL_FLAG_CYCLIC) == 0)
221                         {
222                                 OperationDepsNode *from = (OperationDepsNode *)rel->from;
223                                 IDDepsNode *id_from_node = from->owner->owner;
224                                 if ((id_from_node->layers & layers) != 0 &&
225                                     (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
226                                 {
227                                         ++node->num_links_pending;
228                                 }
229                         }
230                 }
231         }
232 }
233
234 static void calculate_pending_parents(Depsgraph *graph, int layers)
235 {
236         const int num_operations = graph->operations.size();
237         const bool do_threads = num_operations > 256;
238         CalculatePengindData data;
239         data.graph = graph;
240         data.layers = layers;
241         BLI_task_parallel_range(0,
242                                 num_operations,
243                                 &data,
244                                 calculate_pending_func,
245                                 do_threads);
246 }
247
248 #ifdef USE_EVAL_PRIORITY
249 static void calculate_eval_priority(OperationDepsNode *node)
250 {
251         if (node->done) {
252                 return;
253         }
254         node->done = 1;
255
256         if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
257                 /* XXX standard cost of a node, could be estimated somewhat later on */
258                 const float cost = 1.0f;
259                 /* NOOP nodes have no cost */
260                 node->eval_priority = node->is_noop() ? cost : 0.0f;
261
262                 foreach (DepsRelation *rel, node->outlinks) {
263                         OperationDepsNode *to = (OperationDepsNode *)rel->to;
264                         BLI_assert(to->type == DEPSNODE_TYPE_OPERATION);
265                         calculate_eval_priority(to);
266                         node->eval_priority += to->eval_priority;
267                 }
268         }
269         else {
270                 node->eval_priority = 0.0f;
271         }
272 }
273 #endif
274
275 /* Schedule a node if it needs evaluation.
276  *   dec_parents: Decrement pending parents count, true when child nodes are
277  *                scheduled after a task has been completed.
278  */
279 static void schedule_node(TaskPool *pool, Depsgraph *graph, int layers,
280                           OperationDepsNode *node, bool dec_parents,
281                           const int thread_id)
282 {
283         int id_layers = node->owner->owner->layers;
284
285         if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 &&
286             (id_layers & layers) != 0)
287         {
288                 if (dec_parents) {
289                         BLI_assert(node->num_links_pending > 0);
290                         atomic_sub_uint32(&node->num_links_pending, 1);
291                 }
292
293                 if (node->num_links_pending == 0) {
294                         bool is_scheduled = atomic_fetch_and_or_uint8(
295                                 (uint8_t *)&node->scheduled, (uint8_t)true);
296                         if (!is_scheduled) {
297                                 if (node->is_noop()) {
298                                         /* skip NOOP node, schedule children right away */
299                                         schedule_children(pool, graph, node, layers, thread_id);
300                                 }
301                                 else {
302                                         /* children are scheduled once this task is completed */
303                                         BLI_task_pool_push_from_thread(pool,
304                                                                        deg_task_run_func,
305                                                                        node,
306                                                                        false,
307                                                                        TASK_PRIORITY_LOW,
308                                                                        thread_id);
309                                 }
310                         }
311                 }
312         }
313 }
314
315 static void schedule_graph(TaskPool *pool,
316                            Depsgraph *graph,
317                            const int layers)
318 {
319         foreach (OperationDepsNode *node, graph->operations) {
320                 schedule_node(pool, graph, layers, node, false, 0);
321         }
322 }
323
324 static void schedule_children(TaskPool *pool,
325                               Depsgraph *graph,
326                               OperationDepsNode *node,
327                               const int layers,
328                               const int thread_id)
329 {
330         foreach (DepsRelation *rel, node->outlinks) {
331                 OperationDepsNode *child = (OperationDepsNode *)rel->to;
332                 BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
333                 if (child->scheduled) {
334                         /* Happens when having cyclic dependencies. */
335                         continue;
336                 }
337                 schedule_node(pool,
338                               graph,
339                               layers,
340                               child,
341                               (rel->flag & DEPSREL_FLAG_CYCLIC) == 0,
342                               thread_id);
343         }
344 }
345
346 /**
347  * Evaluate all nodes tagged for updating,
348  * \warning This is usually done as part of main loop, but may also be
349  * called from frame-change update.
350  *
351  * \note Time sources should be all valid!
352  */
353 void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
354                              Depsgraph *graph,
355                              const int layers)
356 {
357         /* Generate base evaluation context, upon which all the others are derived. */
358         // TODO: this needs both main and scene access...
359
360         /* Nothing to update, early out. */
361         if (BLI_gset_size(graph->entry_tags) == 0) {
362                 return;
363         }
364
365         /* Set time for the current graph evaluation context. */
366         TimeSourceDepsNode *time_src = graph->find_time_source();
367         eval_ctx->ctime = time_src->cfra;
368
369         /* XXX could use a separate pool for each eval context */
370         DepsgraphEvalState state;
371         state.eval_ctx = eval_ctx;
372         state.graph = graph;
373         state.layers = layers;
374
375         TaskScheduler *task_scheduler = BLI_task_scheduler_get();
376         TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state);
377
378         if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) {
379                 BLI_pool_set_num_threads(task_pool, 1);
380         }
381
382         calculate_pending_parents(graph, layers);
383
384         /* Clear tags. */
385         foreach (OperationDepsNode *node, graph->operations) {
386                 node->done = 0;
387         }
388
389         /* Calculate priority for operation nodes. */
390 #ifdef USE_EVAL_PRIORITY
391         foreach (OperationDepsNode *node, graph->operations) {
392                 calculate_eval_priority(node);
393         }
394 #endif
395
396         DepsgraphDebug::eval_begin(eval_ctx);
397
398         schedule_graph(task_pool, graph, layers);
399
400         BLI_task_pool_work_and_wait(task_pool);
401         BLI_task_pool_free(task_pool);
402
403         DepsgraphDebug::eval_end(eval_ctx);
404
405         /* Clear any uncleared tags - just in case. */
406         deg_graph_clear_tags(graph);
407 }
408
409 }  // namespace DEG