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         CalculatePengindData data;
136         data.graph = graph;
137         ParallelRangeSettings settings;
138         BLI_parallel_range_settings_defaults(&settings);
139         settings.min_iter_per_thread = 1024;
140         BLI_task_parallel_range(0,
141                                 num_operations,
142                                 &data,
143                                 calculate_pending_func,
144                                 &settings);
145 }
146
147 static void initialize_execution(DepsgraphEvalState *state, Depsgraph *graph)
148 {
149         const bool do_stats = state->do_stats;
150         calculate_pending_parents(graph);
151         /* Clear tags and other things which needs to be clear. */
152         foreach (OperationDepsNode *node, graph->operations) {
153                 node->done = 0;
154                 if (do_stats) {
155                         node->stats.reset_current();
156                 }
157         }
158 }
159
160 /* Schedule a node if it needs evaluation.
161  *   dec_parents: Decrement pending parents count, true when child nodes are
162  *                scheduled after a task has been completed.
163  */
164 static void schedule_node(TaskPool *pool, Depsgraph *graph,
165                           OperationDepsNode *node, bool dec_parents,
166                           const int thread_id)
167 {
168         if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) {
169                 if (dec_parents) {
170                         BLI_assert(node->num_links_pending > 0);
171                         atomic_sub_and_fetch_uint32(&node->num_links_pending, 1);
172                 }
173
174                 if (node->num_links_pending == 0) {
175                         bool is_scheduled = atomic_fetch_and_or_uint8(
176                                 (uint8_t *)&node->scheduled, (uint8_t)true);
177                         if (!is_scheduled) {
178                                 if (node->is_noop()) {
179                                         /* skip NOOP node, schedule children right away */
180                                         schedule_children(pool, graph, node, thread_id);
181                                 }
182                                 else {
183                                         /* children are scheduled once this task is completed */
184                                         BLI_task_pool_push_from_thread(pool,
185                                                                        deg_task_run_func,
186                                                                        node,
187                                                                        false,
188                                                                        TASK_PRIORITY_HIGH,
189                                                                        thread_id);
190                                 }
191                         }
192                 }
193         }
194 }
195
196 static void schedule_graph(TaskPool *pool, Depsgraph *graph)
197 {
198         foreach (OperationDepsNode *node, graph->operations) {
199                 schedule_node(pool, graph, node, false, 0);
200         }
201 }
202
203 static void schedule_children(TaskPool *pool,
204                               Depsgraph *graph,
205                               OperationDepsNode *node,
206                               const int thread_id)
207 {
208         foreach (DepsRelation *rel, node->outlinks) {
209                 OperationDepsNode *child = (OperationDepsNode *)rel->to;
210                 BLI_assert(child->type == DEG_NODE_TYPE_OPERATION);
211                 if (child->scheduled) {
212                         /* Happens when having cyclic dependencies. */
213                         continue;
214                 }
215                 schedule_node(pool,
216                               graph,
217                               child,
218                               (rel->flag & DEPSREL_FLAG_CYCLIC) == 0,
219                               thread_id);
220         }
221 }
222
223 /**
224  * Evaluate all nodes tagged for updating,
225  * \warning This is usually done as part of main loop, but may also be
226  * called from frame-change update.
227  *
228  * \note Time sources should be all valid!
229  */
230 void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
231                              Depsgraph *graph)
232 {
233         /* Nothing to update, early out. */
234         if (BLI_gset_len(graph->entry_tags) == 0) {
235                 return;
236         }
237         const bool do_time_debug = ((G.debug & G_DEBUG_DEPSGRAPH_TIME) != 0);
238         const double start_time = do_time_debug ? PIL_check_seconds_timer() : 0;
239         /* Set time for the current graph evaluation context. */
240         TimeSourceDepsNode *time_src = graph->find_time_source();
241         eval_ctx->depsgraph = (::Depsgraph *)graph;
242         eval_ctx->view_layer = DEG_get_evaluated_view_layer((::Depsgraph *)graph);
243         eval_ctx->ctime = time_src->cfra;
244         /* Set up evaluation context for depsgraph itself. */
245         DepsgraphEvalState state;
246         state.eval_ctx = eval_ctx;
247         state.graph = graph;
248         state.do_stats = do_time_debug;
249         /* Set up task scheduler and pull for threaded evaluation. */
250         TaskScheduler *task_scheduler;
251         bool need_free_scheduler;
252         if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) {
253                 task_scheduler = BLI_task_scheduler_create(1);
254                 need_free_scheduler = true;
255         }
256         else {
257                 task_scheduler = BLI_task_scheduler_get();
258                 need_free_scheduler = false;
259         }
260         TaskPool *task_pool = BLI_task_pool_create_suspended(task_scheduler, &state);
261         /* Prepare all nodes for evaluation. */
262         initialize_execution(&state, graph);
263         /* Do actual evaluation now. */
264         schedule_graph(task_pool, graph);
265         BLI_task_pool_work_and_wait(task_pool);
266         BLI_task_pool_free(task_pool);
267         /* Finalize statistics gathering. This is because we only gather single
268          * operation timing here, without aggregating anything to avoid any extra
269          * synchronization.
270          */
271         if (state.do_stats) {
272                 deg_eval_stats_aggregate(graph);
273         }
274         /* Clear any uncleared tags - just in case. */
275         deg_graph_clear_tags(graph);
276         if (need_free_scheduler) {
277                 BLI_task_scheduler_free(task_scheduler);
278         }
279         if (do_time_debug) {
280                 printf("Depsgraph updated in %f seconds.\n",
281                        PIL_check_seconds_timer() - start_time);
282         }
283 }
284
285 }  // namespace DEG