Incorrect derivative produced when array is passed to call expression inside a loop

[parth-07]

Minimal reproducible example:

void modify(double& elem, double val) {
  elem = val;
}

double fn(double i, double j) {
  double arr[5] = {};
  for (int idx = 0; idx < 5; ++idx) {
    modify(arr[idx], i);
  }
  return arr[0] + arr[1] + arr[2] + arr[3] + arr[4];
}

int main() {
  auto fn_grad = clad::gradient(fn);
  double d_i, d_j;
  d_i = d_j = 0;
  fn_grad.execute(3, 5, &d_i, &d_j);
  std::cout << "d_i: " << d_i << "\n";
}

Expected output: d_i: 5
Actual output: d_i: 1

Derived functions generated by Clad:

void modify_pullback(double &elem, double val, clad::array_ref<double> _d_elem, clad::array_ref<double> _d_val) {
    elem = val;
    {
        double _r_d0 = * _d_elem;
        * _d_val += _r_d0;
        * _d_elem -= _r_d0;
        * _d_elem;
    }
}
void fn_grad(double i, double j, clad::array_ref<double> _d_i, clad::array_ref<double> _d_j) {
    clad::array<double> _d_arr(5UL);
    unsigned long _t0;
    int _d_idx = 0;
    clad::tape<int> _t1 = {};
    clad::tape<double> _t3 = {};
    clad::tape<int> _t4 = {};
    clad::tape<double> _t6 = {};
    double arr[5] = {};
    _t0 = 0;
    for (int idx = 0; idx < 5; ++idx) {
        _t0++;
        clad::push(_t3, arr[clad::push(_t1, idx)]);
        modify(arr[clad::push(_t4, idx)], clad::push(_t6, i));
    }
    double fn_return = arr[0] + arr[1] + arr[2] + arr[3] + arr[4];
    goto _label0;
  _label0:
    {
        _d_arr[0] += 1;
        _d_arr[1] += 1;
        _d_arr[2] += 1;
        _d_arr[3] += 1;
        _d_arr[4] += 1;
    }
    for (; _t0; _t0--) {
        {
            double _r1 = clad::pop(_t3);
            double _grad1 = 0.;
            modify_pullback(_r1, clad::pop(_t6), &_d_arr[_t2], &_grad1); <------------- Interesting line
            double _r0 = _d_arr[_t2];
            double _r2 = _grad1;
            * _d_i += _r2;
        }
    }
}

Root cause of the error

Please consider the line marked as an interesting line in the above code snippet. Derivative of arr[idx] as returned by Visit(...) is the expression: _d_arr[_t2]. But _t2 is not declared or initialised anywhere in the program.

[ShounakDas101]

This issue #441 seems very similar to issue #465. It appears that the variables _t2 and _t5 are being generated by the VisitArraySubscriptExpr() function in ReverseModeVisitor.cpp. However, currently, these two variables are not being added to the block label0. Even if we enter the if(dfdx()) block in VisitArraySubscriptExpr(), _t2 and _t5 are generated after modify_pullback() is called, as shown below:

modify_pullback(_r1, clad::pop(_t6), &_d_arr[_t2], &_grad1);
    int _t2 = clad::pop(_t1);
    double _r0 = _d_arr[_t2];
    int _t5 = clad::pop(_t4);

To resolve this issue, we need to add _t2 and _t5 to the block label0 before calling modify_pullback().
Can you Please provide few suggestions

[vgvassilev]

@vaithak, do you think you can take a look and propose a fix for this?

[ShounakDas101]

In my PR:

1. The result of all the test cases are maching.
2. I believe my changes result in the correct fn4_grad, but it does not match the expected result because the positions of a few terms (_t4 and _t7) have been shifted. I don't think these changes will cause any problems.
3. The order in which terms are generated has been changed, but the generated code is same as expected.(e.g., _t4 in this case as shown below).
4. An unnecessary term (_t7) is not generated in my solution.

All the solutions match for my proposed solution, but GitHub is giving an error for the function fn4 in FunctionCalls.c, specifically.

double fn4(double* arr, int n) {
double res = 0;
res += sum(arr, n);
for (int i=0; i<n; ++i) {
twice(arr[i]);
res += arr[i];
}
return res;
}

fn4_grad created by my PR:-

The code is:
void fn4_grad(double *arr, int n, clad::array_ref _d_arr, clad::array_ref _d_n) {
double _d_res = 0;
double *_t0;
int _t1;
unsigned long _t2;
int _d_i = 0;
clad::tape _t3 = {};
clad::tape _t5 = {};
clad::tape _t6 = {};
clad::tape _t8 = {};
int _t10;
double res = 0;
_t0 = arr;
_t1 = n;
res += sum(arr, _t1);
_t2 = 0;
for (int i = 0; i < n; ++i) {
_t2++;
clad::push(_t5, arr[clad::push(_t3, i)]);
twice(arr[clad::push(_t6, i)]);
res += arr[clad::push(_t8, i)];
}
_t10 = n - 1;
res = arr[_t10];
double fn4_return = res;
goto _label0;
_label0:
_d_res += 1;
{
double _r_d2 = _d_res;
_d_arr[_t10] += _r_d2;
_d_res -= _r_d2;
}
for (; _t2; _t2--) {
{
double _r_d1 = _d_res;
_d_res += _r_d1;
int _t9 = clad::pop(_t8);
_d_arr[_t9] += _r_d1;
_d_res -= _r_d1;
}
{
int _t4 = clad::pop(_t3); -----------------> _t4 generated here
double _r3 = clad::pop(_t5);
twice_pullback(_r3, &_d_arr[_t4]);
double _r2 = _d_arr[_t4];
}
}
{
double _r_d0 = _d_res;
_d_res += _r_d0;
int _grad1 = 0;
sum_pullback(_t0, _t1, _r_d0, _d_arr, &_grad1);
clad::array _r0(_d_arr);
int _r1 = _grad1;
* _d_n += _r1;
_d_res -= _r_d0;
}
}

Old programs solution :-

The code is:
void fn4_grad(double *arr, int n, clad::array_ref _d_arr, clad::array_ref _d_n) {
double _d_res = 0;
double *_t0;
int _t1;
unsigned long _t2;
int _d_i = 0;
clad::tape _t3 = {};
clad::tape _t5 = {};
clad::tape _t6 = {};
clad::tape _t8 = {};
int _t10;
double res = 0;
_t0 = arr;
_t1 = n;
res += sum(arr, _t1);
_t2 = 0;
for (int i = 0; i < n; ++i) {
_t2++;
clad::push(_t5, arr[clad::push(_t3, i)]);
twice(arr[clad::push(_t6, i)]);
res += arr[clad::push(_t8, i)];
}
_t10 = n - 1;
res = arr[_t10];
double fn4_return = res;
goto _label0;
_label0:
_d_res += 1;
{
double _r_d2 = _d_res;
_d_arr[_t10] += _r_d2;
_d_res -= _r_d2;
}
for (; _t2; _t2--) {
{
int _t7 = clad::pop(_t6); ------------>Not required so not generated
int _t4 = clad::pop(_t3); ------------>Shifted below
double _r_d1 = _d_res;
_d_res += _r_d1;
int _t9 = clad::pop(_t8);
_d_arr[_t9] += _r_d1;
_d_res -= _r_d1;
}
{
double _r3 = clad::pop(_t5);
twice_pullback(_r3, &_d_arr[_t4]);
double _r2 = _d_arr[_t4];
}
}
{
double _r_d0 = _d_res;
_d_res += _r_d0;
int _grad1 = 0;
sum_pullback(_t0, _t1, _r_d0, _d_arr, &_grad1);
clad::array _r0(_d_arr);
int _r1 = _grad1;
* _d_n += _r1;
_d_res -= _r_d0;
}
}

[vgvassilev]

@ShounakDas101, I have looked at the PR and it still fails in some tests. The fix you proposed there seems more like a workaround rather than an actual solution. Maybe @parth-07 can correct me if I am wrong but we need "just" to declare the variable before its first use.

[ShounakDas101]

@parth-07 , I have run FunctionCalls.c locally, and all the results have matched. As far as I have tested, the variables are declared before their first use. In the codecov report, I could only see one error, but it actually gives the correct result in the end. This is true for all the test cases in FunctionCalls.c. If you can provide me with the functions that are causing errors, it will help me in resolving the issue.

[vgvassilev]

Fixed in #655