Coverage Report

Created: 2019-07-03 22:50

/home/liu/buildslave/linux-x64-runtests/build/lib/nnc/ccv_nnc_dynamic_graph_backward.c
Line
Count
Source (jump to first uncovered line)
1
#include "ccv_nnc.h"
2
#include "ccv_nnc_easy.h"
3
#include "ccv_nnc_internal.h"
4
#include "ccv_nnc_easy.h"
5
#include "ccv_internal.h"
6
#include "_ccv_nnc_dynamic_graph.h"
7
8
#pragma mark - Level-4.5 API
9
10
void ccv_nnc_dynamic_graph_backward(ccv_nnc_dynamic_graph_t* const dynamic_graph, const ccv_nnc_tensor_variable_t f_variable, const ccv_nnc_tensor_variable_t df_optional, const ccv_nnc_tensor_variable_t* const inputs, const int input_size, ccv_nnc_tensor_variable_t* const outputs, const int output_size)
11
8
{
12
8
  int d, i, j, k;
13
8
  assert(input_size == output_size);
14
8
  assert(input_size > 0);
15
8
  assert(output_size > 0);
16
8
  // Both f_variable and tensor_variable should be, at least, executed. Otherwise we cannot differentiate.
17
8
  assert(f_variable->symbol.d >= 0);
18
8
  const ccv_nnc_tensor_variable_graph_bind_t* const f_symbol_extra = (ccv_nnc_tensor_variable_graph_bind_t*)ccv_array_get(dynamic_graph->binds, f_variable->symbol.d);
19
8
  assert(f_symbol_extra->sources && f_symbol_extra->sources->rnum > 0);
20
17
  
for (i = 0; 8
i < input_size;
i++9
)
21
9
  {
22
9
    assert(inputs[i]->type != CCV_NNC_TENSOR_CONSTANT);
23
9
    assert(inputs[i]->symbol.d >= 0);
24
9
    assert(((ccv_nnc_tensor_variable_graph_bind_t*)ccv_array_get(dynamic_graph->binds, inputs[i]->symbol.d))->destinations &&
25
9
      ((ccv_nnc_tensor_variable_graph_bind_t*)ccv_array_get(dynamic_graph->binds, inputs[i]->symbol.d))->destinations->rnum > 0);
26
9
  }
27
8
  // Fill in the symbol info for outputs.
28
17
  
for (i = 0; 8
i < output_size;
i++9
)
29
9
    if (ccv_nnc_is_tensor_auto(outputs[i]->info))
30
5
      outputs[i]->info = inputs[i]->info;
31
8
  const int exec_symbol_info_size = ccv_nnc_graph_exec_symbol_count(dynamic_graph->tape);
32
8
  ccv_array_t* const sources = ccv_array_new(sizeof(ccv_nnc_graph_exec_symbol_t), 1, 0);
33
8
  if (!dynamic_graph->ws)
34
5
    dynamic_graph->ws = ccv_array_new(sizeof(int), exec_symbol_info_size * 2 + ((exec_symbol_info_size + 31) >> 5), 0);
35
8
  ccv_array_t* const ws = dynamic_graph->ws;
36
8
  ccv_array_resize(ws, exec_symbol_info_size * 2 + ((exec_symbol_info_size + 31) >> 5));
37
8
  // set visited to all 0.
38
8
  memset((uint32_t*)ccv_array_get(ws, exec_symbol_info_size * 2), 0, sizeof(uint32_t) * ((exec_symbol_info_size + 31) >> 5));
39
17
  for (i = 0; i < input_size; 
i++9
)
40
9
  {
41
9
    ccv_array_t* const destinations = ((ccv_nnc_tensor_variable_graph_bind_t*)ccv_array_get(dynamic_graph->binds, inputs[i]->symbol.d))->destinations;
42
24
    for (j = 0; j < destinations->rnum; 
j++15
)
43
15
      ccv_nnc_insert_if_prior_to_any(dynamic_graph->tape,
44
15
        *(int*)ccv_array_get(destinations, j),
45
15
        sources, (uint32_t*)ccv_array_get(ws, exec_symbol_info_size * 2),
46
15
        (int*)ccv_array_get(ws, 0), (int*)ccv_array_get(ws, exec_symbol_info_size));
47
9
  }
48
8
  ccv_array_t* const destinations = ccv_array_new(sizeof(ccv_nnc_graph_exec_symbol_t), f_symbol_extra->sources->rnum, 0);
49
8
  ccv_array_resize(destinations, f_symbol_extra->sources->rnum);
50
18
  for (i = 0; i < destinations->rnum; 
i++10
)
51
10
  {
52
10
    ccv_nnc_graph_exec_symbol_t* const symbol = (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(destinations, i);
53
10
    symbol->d = *(int*)ccv_array_get(f_symbol_extra->sources, i);
54
10
    symbol->graph = dynamic_graph->tape;
55
10
  }
56
8
  // Go over sources, because destinations will get removed all the time, thus, the index is not accurate.
57
8
  if (destinations->rnum > 1)
58
4
    
for (i = 0 ; 1
i < f_symbol_extra->sources->rnum;
i++3
)
59
3
    {
60
3
      memset((uint32_t*)ccv_array_get(ws, exec_symbol_info_size * 2), 0, sizeof(uint32_t) * ((exec_symbol_info_size + 31) >> 5));
61
3
      ccv_nnc_remove_if_prior_to_any(dynamic_graph->tape,
62
3
        *(int*)ccv_array_get(f_symbol_extra->sources, i),
63
3
        destinations, (uint32_t*)ccv_array_get(ws, exec_symbol_info_size * 2),
64
3
        (int*)ccv_array_get(ws, 0), (int*)ccv_array_get(ws, exec_symbol_info_size));
65
3
    }
66
8
  ccv_nnc_tensor_symbol_t input_symbols[input_size];
67
17
  for (i = 0; i < input_size; 
i++9
)
68
9
    input_symbols[i] = inputs[i]->symbol;
69
8
  ccv_array_t* const symbol_stack = ccv_array_new(sizeof(ccv_nnc_tape_symbol_t), 1, 0);
70
8
  ccv_nnc_tensor_symbol_new_hook(dynamic_graph->tape, ccv_nnc_dynamic_graph_push_backward_tensor_symbol, symbol_stack);
71
8
  ccv_nnc_tensor_symbol_alias_new_hook(dynamic_graph->tape, ccv_nnc_dynamic_graph_push_backward_tensor_symbol_alias, symbol_stack);
72
8
  ccv_nnc_graph_exec_symbol_new_hook(dynamic_graph->tape, ccv_nnc_dynamic_graph_push_backward_graph_exec_symbol, symbol_stack);
73
8
  ccv_nnc_symbolic_graph_backward(dynamic_graph->tape,
74
8
    &f_variable->symbol, 1, input_symbols, input_size,
75
8
    (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(sources, 0), sources->rnum,
76
8
    (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(destinations, 0), destinations->rnum);
77
8
  ccv_nnc_tensor_symbol_new_hook(dynamic_graph->tape, 0, 0);
78
8
  ccv_nnc_tensor_symbol_alias_new_hook(dynamic_graph->tape, 0, 0);
79
8
  ccv_nnc_graph_exec_symbol_new_hook(dynamic_graph->tape, 0, 0);
80
8
  // Bind generated tensors.
81
8
  ccv_array_t* const tensor_binds = ccv_array_new(sizeof(ccv_nnc_tensor_bind_t), dynamic_graph->vars->rnum + 2, 0);
82
60
  for (i = 0; i < dynamic_graph->vars->rnum; 
i++52
)
83
52
  {
84
52
    ccv_nnc_tensor_variable_t var = *(ccv_nnc_tensor_variable_t*)ccv_array_get(dynamic_graph->vars, i);
85
52
    if (var && var->tensor_view && 
var->symbol.d >= 047
)
86
38
    {
87
38
      ccv_nnc_tensor_bind_t bind = {
88
38
        .symbol = var->symbol,
89
38
        .tensor = (ccv_nnc_tensor_t*)CCV_NNC_TENSOR_VIEW(var->tensor_view)
90
38
      };
91
38
      ccv_array_push(tensor_binds, &bind);
92
38
    }
93
52
  }
94
58
  for (i = 0; i < dynamic_graph->binds->rnum; 
i++50
)
95
50
  {
96
50
    ccv_nnc_tensor_variable_graph_bind_t* const bind = (ccv_nnc_tensor_variable_graph_bind_t*)ccv_array_get(dynamic_graph->binds, i);
97
50
    if (bind->index == CCV_NNC_TENSOR_NO_VARIABLE_BUT_USED && 
bind->tensor_view12
)
98
12
    {
99
12
      ccv_nnc_tensor_bind_t b = {
100
12
        .symbol = {
101
12
          .d = i,
102
12
          .graph = dynamic_graph->tape,
103
12
        },
104
12
        .tensor = (ccv_nnc_tensor_t*)CCV_NNC_TENSOR_VIEW(bind->tensor_view)
105
12
      };
106
12
      ccv_array_push(tensor_binds, &b);
107
12
    }
108
50
  }
109
8
  // Compiled graph comes from the df.
110
8
  ccv_array_clear(sources);
111
8
  const ccv_nnc_tensor_symbol_t df = ccv_nnc_tensor_symbol_for_backward(dynamic_graph->tape, f_variable->symbol);
112
8
  assert(df.d >= 0);
113
16
  
for (d = 0; 8
d < destinations->rnum;
d++8
)
114
8
  {
115
8
    const ccv_nnc_graph_exec_symbol_t* const destination = (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(destinations, d);
116
8
    const int* outgoings; int outgoing_size;
117
8
    ccv_nnc_graph_exec_symbol_to(dynamic_graph->tape, *destination, &outgoings, &outgoing_size);
118
16
    for (i = 0; i < outgoing_size; 
i++8
)
119
8
    {
120
8
      const int exec_idx = outgoings[i];
121
8
      const int* inputs; int input_size;
122
8
      ccv_nnc_graph_exec_symbol_io(dynamic_graph->tape, (ccv_nnc_graph_exec_symbol_t){
123
8
        .d = exec_idx,
124
8
        .graph = dynamic_graph->tape
125
8
      }, &inputs, &input_size, 0, 0);
126
8
      for (j = 0; j < input_size; 
j++0
)
127
8
      {
128
8
        const int input = inputs[j];
129
8
        const int alias_ref = input >= 0 ? ccv_nnc_tensor_symbol_alias_to(dynamic_graph->tape, (ccv_nnc_tensor_symbol_t){
130
8
          .d = input,
131
8
          .graph = dynamic_graph->tape
132
8
        }).d : 
CCV_NNC_NO_TENSOR_SYMBOL0
; // This could be CCV_NNC_NO_TENSOR_SYMBOL, which is negative.
133
8
        // alias_ref is either exists, or -1.
134
8
        if (df.d == input || 
df.d == alias_ref1
)
135
8
        {
136
8
          int flag = 0;
137
8
          for (k = 0; !flag && k < sources->rnum; 
k++0
)
138
0
            flag = (exec_idx == ((ccv_nnc_graph_exec_symbol_t*)ccv_array_get(sources, k))->d);
139
8
          if (!flag)
140
8
          {
141
8
            const ccv_nnc_graph_exec_symbol_t source = {
142
8
              .d = exec_idx,
143
8
              .graph = dynamic_graph->tape
144
8
            };
145
8
            ccv_array_push(sources, &source);
146
8
          }
147
8
          break;
148
8
        }
149
8
      }
150
8
    }
151
8
  }
152
8
  int freeable_size = 0;
153
8
  ccv_nnc_tensor_variable_t freeables[output_size];
154
8
  // Bind dt tensor.
155
17
  for (i = 0; i < output_size; 
i++9
)
156
9
  {
157
9
    const ccv_nnc_tensor_symbol_t symbol = ccv_nnc_tensor_symbol_for_backward(dynamic_graph->tape, input_symbols[i]);
158
9
    if (outputs[i]->symbol.d >= 0)
159
1
      freeables[freeable_size++] = ccv_nnc_tensor_variable_exchange_new(dynamic_graph, outputs[i]);
160
9
    ccv_nnc_tensor_t* tensor = ccv_nnc_tensor_from_variable(dynamic_graph, outputs[i]);
161
9
    const ccv_nnc_tensor_bind_t dt_bind = {
162
9
      .symbol = symbol,
163
9
      .tensor = tensor
164
9
    };
165
9
    ccv_array_push(tensor_binds, &dt_bind);
166
9
  }
167
8
  ccv_array_clear(destinations);
168
17
  for (i = 0; i < output_size; 
i++9
)
169
9
  {
170
9
    const ccv_nnc_tensor_symbol_t symbol = ccv_nnc_tensor_symbol_for_backward(dynamic_graph->tape, input_symbols[i]);
171
9
    const ccv_nnc_graph_exec_symbol_t destination = ccv_nnc_graph_exec_symbol_for_backward(dynamic_graph->tape, symbol);
172
9
    ccv_array_push(destinations, &destination);
173
9
  }
174
8
  ccv_nnc_graph_t* graph = 0;
175
8
  ccv_nnc_tensor_arena_t* tensor_arena = 0;
176
8
  ccv_nnc_graph_exec_arena_t* exec_arena = 0;
177
8
  // TODO: Should apply simplification right after the backward pass generated.
178
8
  if (df_optional)
179
2
  {
180
2
    // If provided df variable, no need to set to all ones.
181
2
    const ccv_nnc_tensor_bind_t df_bind = {
182
2
      .symbol = df,
183
2
      .tensor = ccv_nnc_tensor_from_variable(dynamic_graph, df_optional)
184
2
    };
185
2
    ccv_array_push(tensor_binds, &df_bind);
186
2
    ccv_nnc_symbolic_graph_compile(dynamic_graph->tape,
187
2
      (ccv_nnc_tensor_bind_t*)ccv_array_get(tensor_binds, 0), tensor_binds->rnum,
188
2
      0, 0,
189
2
      (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(sources, 0), sources->rnum,
190
2
      (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(destinations, 0), destinations->rnum,
191
2
      &graph, &tensor_arena, &exec_arena);
192
2
    ccv_array_free(sources);
193
6
  } else {
194
6
    ccv_nnc_graph_exec_symbol_t set_ones = ccv_nnc_graph_exec_symbol_new(dynamic_graph->tape, CMD_SET_FORWARD(1), 0, 0, &df, 1, 0);
195
12
    for (i = 0; i < sources->rnum; 
i++6
)
196
6
      ccv_nnc_graph_exec_symbol_concat(dynamic_graph->tape, set_ones, *(ccv_nnc_graph_exec_symbol_t*)ccv_array_get(sources, i));
197
6
    ccv_array_free(sources);
198
6
    ccv_nnc_symbolic_graph_compile(dynamic_graph->tape,
199
6
      (ccv_nnc_tensor_bind_t*)ccv_array_get(tensor_binds, 0), tensor_binds->rnum,
200
6
      0, 0,
201
6
      &set_ones, 1,
202
6
      (ccv_nnc_graph_exec_symbol_t*)ccv_array_get(destinations, 0), destinations->rnum,
203
6
      &graph, &tensor_arena, &exec_arena);
204
6
    ccv_nnc_graph_exec_symbol_free(dynamic_graph->tape, set_ones);
205
6
  }
206
8
  ccv_array_free(destinations);
207
8
  ccv_array_free(tensor_binds);
208
8
  // TODO: Should apply static schedule before run the graph.
209
8
  ccv_nnc_graph_run(graph, 0, 0, 0, TRAVERSE_FULL);
210
8
  ccv_nnc_graph_free(graph);
211
8
  ccv_nnc_tensor_arena_free(tensor_arena);
212
8
  ccv_nnc_graph_exec_arena_free(exec_arena);
213
8
  // Remove newly added symbols to restore the graph.
214
93
  for (i = 0; i < symbol_stack->rnum; 
i++85
)
215
85
  {
216
85
    const ccv_nnc_tape_symbol_t* const symbol = (ccv_nnc_tape_symbol_t*)ccv_array_get(symbol_stack, i);
217
85
    if (symbol->type == CCV_NNC_SYMBOL_TENSOR || 
symbol->type == CCV_NNC_SYMBOL_TENSOR_ALIAS33
)
218
58
      ccv_nnc_tensor_symbol_free(dynamic_graph->tape, (ccv_nnc_tensor_symbol_t){
219
58
        .d = symbol->d,
220
58
        .graph = dynamic_graph->tape
221
58
      });
222
27
    else if (symbol->type == CCV_NNC_SYMBOL_GRAPH_EXEC)
223
27
      ccv_nnc_graph_exec_symbol_free(dynamic_graph->tape, (ccv_nnc_graph_exec_symbol_t){
224
27
        .d = symbol->d,
225
27
        .graph = dynamic_graph->tape
226
27
      });
227
85
  }
228
8
  // Now, able to free some of the reused outputs. This need to be the last step otherwise some of the exec symbols
229
8
  // above may be freed by this operation.
230
9
  for (i = 0; i < freeable_size; 
i++1
)
231
1
    ccv_nnc_tensor_variable_free(dynamic_graph, freeables[i]);
232
8
  ccv_array_free(symbol_stack);
233
8
}