clad
clad copied to clipboard
vgvassilev
Optimize away redundant goto statements
In many cases we have:
...
goto _label0;
_label0:
...
We should optimize away this redundancy in the output and that would simplify taking the higher order derivative of the produced code.
@vgvassilev using while loop which loop should run in the o(nlogn) by using binary loop
Hello @vgvassilev @parth-07
To optimize away the redundancy in the output, we can use a single label and then reference it with the ampersand operator. Like this:
...
myLabel:
...
goto &myLabel;
...
This will make the code more efficient and make it easier to take higher order derivatives.
Hi @ro4i7
Can you please explain how it will make code more efficient and make it easier to take higher-order derivatives?
Hi @ro4i7
Can you please explain how it will make code more efficient and make it easier to take higher-order derivatives?
yeah sure, The use of a single label and the ampersand operator to reference it can make code more efficient by reducing redundancy in the output. This is because the use of a single label allows the program to jump back to that point in the code without having to repeat the label multiple times. This can save memory and processing time.
This technique can make it easier to take higher-order derivatives because it allows for more efficient and concise code. In the context of automatic differentiation, for example, the use of a single label can help to reduce the amount of generated code and make the code more maintainable. It also makes it easier to differentiate nested loops and other complex control flow structures.
Upon using clad::differentiate() I did not find and goto statements(atleast for the function I have used). This leads me to conclude that the problem is a mostly applicable for reverse mode AD.
The gradient is computed using reverse-mode automatic differentiation, which involves building a computational graph of the function and then computing the gradients of each node in the graph with respect to the input. It probably uses ReverseModeVisitor.h
The code for the gradient of each node is auto generated and has redundant goto statements( as seen in the pic . please confirm if this is the problem being addressed in the issue). This node is then used to compute the higher order derivatives.
Removing this redundancy would simplify taking the higher order derivative of the produced code.
This generated code has the following redundancy which is mentioned in the issue but I am not sure how this auto code is being generated. I am guessing it takes help from ReverseModeVisitor.h
NOTE: For ForwardMode AD I understand ValueAndPushforward functions and ForwardModeVisitor.h help compute the derivatives of each node in the graph.
Overall I have studied both Forward and Reverse AD but understanding the working of Reverse AD code is proving to be a bit more challenging .
Now I have compiled the following code and ran the code as below to understand how the "goto... Label" redundant code is being generated.
#include "/home/shounak/My_clad/inst/include/clad/Differentiator/Differentiator.h"
#include
double f_add2(double x, double y) { return 3x + 4y; }
void f_add2_grad(double x, double y, clad::array_ref
//void f_add2_grad(double x, double y, clad::array_ref
double f_decls3(double x, double y) {
double a = 3 * x;
double c = 333 * y;
if (x > 1)
return 2 * a;
else if (x < -1)
return -2 * a;
double b = a * a;
return b;
}
void f_decls3_grad(double x, double y, clad::array_ref
#define TEST(F, x, y)
{
result[0] = 0;
result[1] = 0;
clad::gradient(F);
F##_grad(x, y, &result[0], &result[1]);
printf("Result is = {%.2f, %.2f}\n", result[0], result[1]);
}
int main()
{ double result[2];
TEST(f_add2, 1, 1); // CHECK-EXEC: Result is = {3.00, 4.00}
TEST(f_decls3, 3, 0); // CHECK-EXEC: Result is = {6.00, 0.00}
result[0] = 0;
result[1] = 0;
clad::gradient(f_add2);
//f_add2_grad(1, 1, &result[0], &result[1]); // to test the auto generated code is correctly compiling
printf("Result is = {%.2f, %.2f}\n", result[0], result[1]);
result[0] = 0;
result[1] = 0;
auto f = clad::gradient(f_decls3);
f.dump();
f_decls3_grad(3, 0, &result[0], &result[1]);
printf("Result is = {%.2f, %.2f}\n", result[0], result[1]);
return 1;
}
@parth-07
STEP 1: In clad/include/clad/Differentiator/ReverseModeVisitor.h (changes in line number 34 as given below)
class ReverseModeVisitor private: bool if_encounter = false; // this line added
STEP 2: In ReverseModeVisitor.cpp ( Changes in Line number 772 as given below)
StmtDiff ReverseModeVisitor::VisitIfStmt(const clang::IfStmt* If) { if_encounter = true; // this line added
STEP 3: In ReverseModeVisitor.cpp (Changes in line number 1181 as given below)
In StmtDiff ReverseModeVisitor::VisitReturnStmt(const ReturnStmt* RS)
if(if_encounter==true) { if_encounter=false; return m_Sema.ActOnGotoStmt(noLoc, noLoc, LD).get(); } else { return m_Sema.ActOnNullStmt(noLoc).get(); }
MY TEST FUNCTION:
double f_foo(double x, double y) { if (x > y) return x; //conditional return. Hence, goto ..label0 should be in the f_foo_grad() else if(x<y) return y; //conditional return. Hence, goto ..label1 should be in the f_foo_grad() return x+y; //non-conditional return. Hence, goto should not be in the f_foo_grad()
}
MY TEST RESULT Automatic Differentiation Reverse Mode, f_foo_grad() :
The f_foo_grad() code is:
void f_foo_grad(double x, double y, clad::array_ref
I have also tested with Gradient.c and all the results were same.
@vgvassilev I have used the ParentMapContext library in my solution, but I believe it may be unavailable in older versions, which is causing some tests to fail. Do I need to make changes to all the test files and remove the 'goto' labels? Additionally, I was unable to run a few test files locally, probably due to CLAD moving into clang 16. However, I have tested all the test files in the Gradient Folder, and they give the correct result.