Generalize collectInductionValues (#3031)

* Generalize collectInductionValues

* Support affine transformations of loop index as induction variables

* Test for generalized induction value collection

* Neaten inductive variable finding

* Store the type of implication success when finding inductive variables

* Test that loop induction finding does not alway succeed

* Support chains of additions and branches of additions in induction variable finding

* Use c++17 for downstream compilers

11 files changed, 234 insertions, 1 deletions

diff --git a/tests/autodiff/long-loop-branching-addition.slang b/tests/autodiff/long-loop-branching-addition.slang
new file mode 100644
index 000000000..beb371bd0
--- /dev/null
+++ b/tests/autodiff/long-loop-branching-addition.slang
@@ -0,0 +1,57 @@
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -shaderobj -output-using-type
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute -shaderobj -output-using-type
+//TEST:SIMPLE(filecheck=CHECK): -target hlsl -profile cs_5_0 -entry computeMain -line-directive-mode none
+
+//TEST_INPUT:ubuffer(data=[0], stride=4):out,name=outputBuffer
+RWStructuredBuffer<float> outputBuffer;
+
+[BackwardDifferentiable]
+float sin_series(float x, int iterations)
+{
+    float result = x;
+    float term = x;
+    int i = 1;
+    [MaxIters(30)]
+    do
+    {
+        term *= -1.0f * x * x / ((2 * i) * (2 * i + 1));
+        result += term;
+        if(result > 1000000)
+        {
+            i += 1;
+            if(result > 2000000)
+            {
+                term += 1;
+                i += 1;
+            }
+            else
+            {
+                i += 1;
+            }
+        }
+        else
+        {
+            i += 2;
+        }
+        i += -1;
+    } while (i < iterations);
+    return result;
+}
+
+// Check that the intermediate context of sin_series does not have an array for `i`.
+// This test inparticular checks that can identify induction variables through
+// branching control flow
+
+// CHECK: struct s_bwd_sin_series_Intermediates
+// CHECK-NOT: int {{[A-Za-z0-9_]+}}[{{.*}}]
+// CHECK: }
+
+[numthreads(1, 1, 1)]
+void computeMain(uint3 dispatchThreadID: SV_DispatchThreadID)
+{
+    var x = diffPair(float.getPi(), 1.0);
+
+    __bwd_diff(sin_series)(x, 30, 1.0f);
+
+    outputBuffer[0] = x.d; // -1.0
+}
diff --git a/tests/autodiff/long-loop-branching-addition.slang.expected.txt b/tests/autodiff/long-loop-branching-addition.slang.expected.txt
new file mode 100644
index 000000000..77bdc5ea4
--- /dev/null
+++ b/tests/autodiff/long-loop-branching-addition.slang.expected.txt
@@ -0,0 +1,2 @@
+type: float
+-1.0
diff --git a/tests/autodiff/long-loop-chained-addition.slang b/tests/autodiff/long-loop-chained-addition.slang
new file mode 100644
index 000000000..8f75744a9
--- /dev/null
+++ b/tests/autodiff/long-loop-chained-addition.slang
@@ -0,0 +1,42 @@
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -shaderobj -output-using-type
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute -shaderobj -output-using-type
+//TEST:SIMPLE(filecheck=CHECK): -target hlsl -profile cs_5_0 -entry computeMain -line-directive-mode none
+
+//TEST_INPUT:ubuffer(data=[0], stride=4):out,name=outputBuffer
+RWStructuredBuffer<float> outputBuffer;
+
+[BackwardDifferentiable]
+float sin_series(float x, int iterations)
+{
+    float result = x;
+    float term = x;
+    int i = 1;
+    [MaxIters(30)]
+    do
+    {
+        term *= -1.0f * x * x / ((2 * i) * (2 * i + 1));
+        i += 2;
+        i++;
+        result += term;
+        i -= 2;
+    } while (i < iterations);
+    return result;
+}
+
+// Check that the intermediate context of sin_series does not have an array for `i`.
+// This test inparticular checks that can identify induction variables with
+// more than one operation applied to them during the loop
+
+// CHECK: struct s_bwd_sin_series_Intermediates
+// CHECK-NOT: int {{[A-Za-z0-9_]+}}[{{.*}}]
+// CHECK: }
+
+[numthreads(1, 1, 1)]
+void computeMain(uint3 dispatchThreadID: SV_DispatchThreadID)
+{
+    var x = diffPair(float.getPi(), 1.0);
+
+    __bwd_diff(sin_series)(x, 30, 1.0f);
+
+    outputBuffer[0] = x.d; // -1.0
+}
diff --git a/tests/autodiff/long-loop-chained-addition.slang.expected.txt b/tests/autodiff/long-loop-chained-addition.slang.expected.txt
new file mode 100644
index 000000000..77bdc5ea4
--- /dev/null
+++ b/tests/autodiff/long-loop-chained-addition.slang.expected.txt
@@ -0,0 +1,2 @@
+type: float
+-1.0
diff --git a/tests/autodiff/long-loop-multiple.slang b/tests/autodiff/long-loop-multiple.slang
new file mode 100644
index 000000000..a696beccf
--- /dev/null
+++ b/tests/autodiff/long-loop-multiple.slang
@@ -0,0 +1,41 @@
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -shaderobj -output-using-type
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute -shaderobj -output-using-type
+//TEST:SIMPLE(filecheck=CHECK): -target hlsl -profile cs_5_0 -entry computeMain -line-directive-mode none
+
+//TEST_INPUT:ubuffer(data=[0], stride=4):out,name=outputBuffer
+RWStructuredBuffer<float> outputBuffer;
+
+[BackwardDifferentiable]
+float sin_series(float x, int iterations)
+{
+    float result = x;
+    float term = x;
+    [MaxIters(30)]
+    for (int i = 1; i < iterations * 10; i += 10)
+    {
+        term *= -1.0f * x * x / ((2 * i / 10 + 1) * (2 * i / 10 + 2));
+        result += term;
+    }
+    return result;
+}
+
+// Check that the intermediate context of sin_series does not have an array for `i`.
+// This test differs from ./long-loop.slang in that the loop counter is
+// relative to a multiple of the loop iteration
+
+// CHECK: struct s_bwd_sin_series_Intermediates
+// CHECK-NOT: int {{[A-Za-z0-9_]+}}[{{.*}}]
+// CHECK: }
+
+[numthreads(1, 1, 1)]
+void computeMain(uint3 dispatchThreadID: SV_DispatchThreadID)
+{
+    var x = diffPair(float.getPi(), 1.0);
+
+    __bwd_diff(sin_series)(x, 30, 1.0f);
+
+    outputBuffer[0] = x.d; // -1.0
+}
+
+
+
diff --git a/tests/autodiff/long-loop-multiple.slang.expected.txt b/tests/autodiff/long-loop-multiple.slang.expected.txt
new file mode 100644
index 000000000..77bdc5ea4
--- /dev/null
+++ b/tests/autodiff/long-loop-multiple.slang.expected.txt
@@ -0,0 +1,2 @@
+type: float
+-1.0
diff --git a/tests/autodiff/long-loop-noninductive.slang b/tests/autodiff/long-loop-noninductive.slang
new file mode 100644
index 000000000..bfd37c4f2
--- /dev/null
+++ b/tests/autodiff/long-loop-noninductive.slang
@@ -0,0 +1,40 @@
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -shaderobj -output-using-type
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute -shaderobj -output-using-type
+//TEST:SIMPLE(filecheck=CHECK): -target hlsl -profile cs_5_0 -entry computeMain -line-directive-mode none
+
+//TEST_INPUT:ubuffer(data=[0], stride=4):out,name=outputBuffer
+RWStructuredBuffer<float> outputBuffer;
+
+[BackwardDifferentiable]
+float sin_series(float x, int iterations)
+{
+    float result = x;
+    float term = x;
+    [MaxIters(35)]
+    for (int i = 1; i < iterations; i++)
+    {
+        if(i == 32)
+            i += 1;
+        term *= -1.0f * x * x / ((2 * i) * (2 * i + 1));
+        result += term;
+    }
+    return result;
+}
+
+// Check that the intermediate context of sin_series still has an array for
+// `i`. This test checks that the induction variable finder doesn't
+// accidentally succeed all the time
+
+// CHECK: struct s_bwd_sin_series_Intermediates
+// CHECK: int {{[A-Za-z0-9_]+}}[{{.*}}]
+// CHECK: }
+
+[numthreads(1, 1, 1)]
+void computeMain(uint3 dispatchThreadID: SV_DispatchThreadID)
+{
+    var x = diffPair(float.getPi(), 1.0);
+
+    __bwd_diff(sin_series)(x, 30, 1.0f);
+
+    outputBuffer[0] = x.d; // -1.0
+}
diff --git a/tests/autodiff/long-loop-noninductive.slang.expected.txt b/tests/autodiff/long-loop-noninductive.slang.expected.txt
new file mode 100644
index 000000000..77bdc5ea4
--- /dev/null
+++ b/tests/autodiff/long-loop-noninductive.slang.expected.txt
@@ -0,0 +1,2 @@
+type: float
+-1.0
diff --git a/tests/autodiff/long-while-loop.slang b/tests/autodiff/long-while-loop.slang
new file mode 100644
index 000000000..20d802e2a
--- /dev/null
+++ b/tests/autodiff/long-while-loop.slang
@@ -0,0 +1,43 @@
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -shaderobj -output-using-type
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute -shaderobj -output-using-type
+//TEST:SIMPLE(filecheck=CHECK): -target hlsl -profile cs_5_0 -entry computeMain -line-directive-mode none
+
+//TEST_INPUT:ubuffer(data=[0], stride=4):out,name=outputBuffer
+RWStructuredBuffer<float> outputBuffer;
+
+[BackwardDifferentiable]
+float sin_series(float x, int iterations)
+{
+    float result = x;
+    float term = x;
+    int i = 1;
+    [MaxIters(30)]
+    do
+    {
+        term *= -1.0f * x * x / ((2 * i) * (2 * i + 1));
+        result += term;
+        i++;
+    } while (i < iterations);
+    return result;
+}
+
+// Check that the intermediate context of sin_series does not have an array for `i`.
+// This differs from ./long-loop.slang in that it uses an equivalent do/while
+// loop, this tests checks that induction variables are still correctly identified.
+
+// CHECK: struct s_bwd_sin_series_Intermediates
+// CHECK-NOT: int {{[A-Za-z0-9_]+}}[{{.*}}]
+// CHECK: }
+
+[numthreads(1, 1, 1)]
+void computeMain(uint3 dispatchThreadID: SV_DispatchThreadID)
+{
+    var x = diffPair(float.getPi(), 1.0);
+
+    __bwd_diff(sin_series)(x, 30, 1.0f);
+
+    outputBuffer[0] = x.d; // -1.0
+}
+
+
+
diff --git a/tests/autodiff/long-while-loop.slang.expected.txt b/tests/autodiff/long-while-loop.slang.expected.txt
new file mode 100644
index 000000000..77bdc5ea4
--- /dev/null
+++ b/tests/autodiff/long-while-loop.slang.expected.txt
@@ -0,0 +1,2 @@
+type: float
+-1.0
diff --git a/tests/cpu-program/cpu-hello-world.slang b/tests/cpu-program/cpu-hello-world.slang
index f91e354bc..f1285f889 100644
--- a/tests/cpu-program/cpu-hello-world.slang
+++ b/tests/cpu-program/cpu-hello-world.slang
@@ -4,4 +4,4 @@ public __extern_cpp int main()
 {
     printf("Hello World.\n");
     return 0;
-}
\ No newline at end of file
+}