Merge branch 'master' into blender2.8
[blender.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/eval/deg_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 #include "BLI_utildefines.h"
38 #include "BLI_task.h"
39 #include "BLI_ghash.h"
40
41 #include "DNA_object_types.h"
42
43 #include "DEG_depsgraph.h"
44 #include "DEG_depsgraph_query.h"
45
46 #include "atomic_ops.h"
47
48 #include "intern/eval/deg_eval_flush.h"
49 #include "intern/eval/deg_eval_stats.h"
50 #include "intern/nodes/deg_node.h"
51 #include "intern/nodes/deg_node_component.h"
52 #include "intern/nodes/deg_node_id.h"
53 #include "intern/nodes/deg_node_operation.h"
54 #include "intern/nodes/deg_node_time.h"
55 #include "intern/depsgraph.h"
56 #include "intern/depsgraph_intern.h"
57
58 #include "util/deg_util_foreach.h"
59
60 namespace DEG {
61
62 /* ********************** */
63 /* Evaluation Entrypoints */
64
65 /* Forward declarations. */
66 static void schedule_children(TaskPool *pool,
67                               Depsgraph *graph,
68                               OperationDepsNode *node,
69                               const int thread_id);
70
71 struct DepsgraphEvalState {
72         EvaluationContext *eval_ctx;
73         Depsgraph *graph;
74         bool do_stats;
75 };
76
77 static void deg_task_run_func(TaskPool *pool,
78                               void *taskdata,
79                               int thread_id)
80 {
81         void *userdata_v = BLI_task_pool_userdata(pool);
82         DepsgraphEvalState *state = (DepsgraphEvalState *)userdata_v;
83         OperationDepsNode *node = (OperationDepsNode *)taskdata;
84         /* Sanity checks. */
85         BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled");
86         /* Perform operation. */
87         if (state->do_stats) {
88                 const double start_time = PIL_check_seconds_timer();
89                 node->evaluate(state->eval_ctx);
90                 node->stats.current_time += PIL_check_seconds_timer() - start_time;
91         }
92         else {
93                 node->evaluate(state->eval_ctx);
94         }
95         /* Schedule children. */
96         BLI_task_pool_delayed_push_begin(pool, thread_id);
97         schedule_children(pool, state->graph, node, thread_id);
98         BLI_task_pool_delayed_push_end(pool, thread_id);
99 }
100
101 typedef struct CalculatePengindData {
102         Depsgraph *graph;
103 } CalculatePengindData;
104
105 static void calculate_pending_func(
106         void *__restrict data_v,
107         const int i,
108         const ParallelRangeTLS *__restrict /*tls*/)
109 {
110         CalculatePengindData *data = (CalculatePengindData *)data_v;
111         Depsgraph *graph = data->graph;
112         OperationDepsNode *node = graph->operations[i];
113
114         node->num_links_pending = 0;
115         node->scheduled = false;
116
117         /* count number of inputs that need updates */
118         if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) {
119                 foreach (DepsRelation *rel, node->inlinks) {
120                         if (rel->from->type == DEG_NODE_TYPE_OPERATION &&
121                             (rel->flag & DEPSREL_FLAG_CYCLIC) == 0)
122                         {
123                                 OperationDepsNode *from = (OperationDepsNode *)rel->from;
124                                 if ((from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) {
125                                         ++node->num_links_pending;
126                                 }
127                         }
128                 }
129         }
130 }
131
132 static void calculate_pending_parents(Depsgraph *graph)
133 {
134         const int num_operations = graph->operations.size();
135         const bool do_threads = (num_operations > 256);
136         CalculatePengindData data;
137         data.graph = graph;
138         ParallelRangeSettings settings;
139         BLI_parallel_range_settings_defaults(&settings);
140         settings.use_threading = do_threads;
141         BLI_task_parallel_range(0,
142                                 num_operations,
143                                 &data,
144                                 calculate_pending_func,
145                                 &settings);
146 }
147
148 static void initialize_execution(DepsgraphEvalState *state, Depsgraph *graph)
149 {
150         const bool do_stats = state->do_stats;
151         calculate_pending_parents(graph);
152         /* Clear tags and other things which needs to be clear. */
153         foreach (OperationDepsNode *node, graph->operations) {
154                 node->done = 0;
155                 if (do_stats) {
156                         node->stats.reset_current();
157                 }
158         }
159 }
160
161 /* Schedule a node if it needs evaluation.
162  *   dec_parents: Decrement pending parents count, true when child nodes are
163  *                scheduled after a task has been completed.
164  */
165 static void schedule_node(TaskPool *pool, Depsgraph *graph,
166                           OperationDepsNode *node, bool dec_parents,
167                           const int thread_id)
168 {
169         if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) {
170                 if (dec_parents) {
171                         BLI_assert(node->num_links_pending > 0);
172                         atomic_sub_and_fetch_uint32(&node->num_links_pending, 1);
173                 }
174
175                 if (node->num_links_pending == 0) {
176                         bool is_scheduled = atomic_fetch_and_or_uint8(
177                                 (uint8_t *)&node->scheduled, (uint8_t)true);
178                         if (!is_scheduled) {
179                                 if (node->is_noop()) {
180                                         /* skip NOOP node, schedule children right away */
181                                         schedule_children(pool, graph, node, thread_id);
182                                 }
183                                 else {
184                                         /* children are scheduled once this task is completed */
185                                         BLI_task_pool_push_from_thread(pool,
186                                                                        deg_task_run_func,
187                                                                        node,
188                                                                        false,
189                                                                        TASK_PRIORITY_HIGH,
190                                                                        thread_id);
191                                 }
192                         }
193                 }
194         }
195 }
196
197 static void schedule_graph(TaskPool *pool, Depsgraph *graph)
198 {
199         foreach (OperationDepsNode *node, graph->operations) {
200                 schedule_node(pool, graph, node, false, 0);
201         }
202 }
203
204 static void schedule_children(TaskPool *pool,
205                               Depsgraph *graph,
206                               OperationDepsNode *node,
207                               const int thread_id)
208 {
209         foreach (DepsRelation *rel, node->outlinks) {
210                 OperationDepsNode *child = (OperationDepsNode *)rel->to;
211                 BLI_assert(child->type == DEG_NODE_TYPE_OPERATION);
212                 if (child->scheduled) {
213                         /* Happens when having cyclic dependencies. */
214                         continue;
215                 }
216                 schedule_node(pool,
217                               graph,
218                               child,
219                               (rel->flag & DEPSREL_FLAG_CYCLIC) == 0,
220                               thread_id);
221         }
222 }
223
224 /**
225  * Evaluate all nodes tagged for updating,
226  * \warning This is usually done as part of main loop, but may also be
227  * called from frame-change update.
228  *
229  * \note Time sources should be all valid!
230  */
231 void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
232                              Depsgraph *graph)
233 {
234         /* Nothing to update, early out. */
235         if (BLI_gset_size(graph->entry_tags) == 0) {
236                 return;
237         }
238         /* Set time for the current graph evaluation context. */
239         TimeSourceDepsNode *time_src = graph->find_time_source();
240         eval_ctx->depsgraph = (::Depsgraph *)graph;
241         eval_ctx->view_layer = DEG_get_evaluated_view_layer((::Depsgraph *)graph);
242         eval_ctx->ctime = time_src->cfra;
243         /* Set up evaluation context for depsgraph itself. */
244         DepsgraphEvalState state;
245         state.eval_ctx = eval_ctx;
246         state.graph = graph;
247         state.do_stats = (G.debug_value != 0);
248         /* Set up task scheduler and pull for threaded evaluation. */
249         TaskScheduler *task_scheduler;
250         bool need_free_scheduler;
251         if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) {
252                 task_scheduler = BLI_task_scheduler_create(1);
253                 need_free_scheduler = true;
254         }
255         else {
256                 task_scheduler = BLI_task_scheduler_get();
257                 need_free_scheduler = false;
258         }
259         TaskPool *task_pool = BLI_task_pool_create_suspended(task_scheduler, &state);
260         /* Prepare all nodes for evaluation. */
261         initialize_execution(&state, graph);
262         /* Do actual evaluation now. */
263         schedule_graph(task_pool, graph);
264         BLI_task_pool_work_and_wait(task_pool);
265         BLI_task_pool_free(task_pool);
266         /* Finalize statistics gathering. This is because we only gather single
267          * operation timing here, without aggregating anything to avoid any extra
268          * synchronization.
269          */
270         if (state.do_stats) {
271                 deg_eval_stats_aggregate(graph);
272         }
273         /* Clear any uncleared tags - just in case. */
274         deg_graph_clear_tags(graph);
275         if (need_free_scheduler) {
276                 BLI_task_scheduler_free(task_scheduler);
277         }
278 }
279
280 }  // namespace DEG