Liveness tracking with phis (#2233)

* #include an absolute path didn't work - because paths were taken to always be relative.

* Refactor Liveness pass, such that locations can be found independently of setting up ranges.

* Refactor around different stages of liveness span analysis.

* WIP Take into account PHI temporaries in liveness tracking.

* WIP First pass of PHI liveness refactor.

* Add BlockIndex.

* WIP Refactor phi liveness around inst runs.

* More improvements around liveness tracking.

* Bug fixes.
Special handling to not add multiple ends, at starts of blocks and after accesses.

* Fix test output.

* Use IRInsertLoc to track insertion point.

* Liveness markers don't have side effects.

* Fix typo in liveness test.

* Small improvements around setting SuccessorResult.

* Fix memory issue around reallocation and RAIIStackArray.
Update test output.

* Update test output for liveness.slang.

* Fix typo in SuccessorResult blockIndex.

* Small tidy up.

* Handle the root start block, correctly scoping the run.

* Split BlockInfo into 'Root' and 'Function'.
Store successors as BlockIndices.

* Tidy up around liveness tracking.

* Add head/tail support to ArrayViews.
Use Count where appropriate.
Use head/tail in liveness impl.

2 files changed, 149 insertions, 36 deletions

diff --git a/tests/experimental/liveness/liveness.slang b/tests/experimental/liveness/liveness.slang
index 70a8c0a24..2e531244e 100644
--- a/tests/experimental/liveness/liveness.slang
+++ b/tests/experimental/liveness/liveness.slang
@@ -26,7 +26,7 @@ int someSlowFunc(int a)
     uint v = a;
     for (int i = 0; i < a * 20; ++i)
     {
-        v = ((v >> 1) || (v << 31)) * i;
+        v = ((v >> 1) | (v << 31)) * i;
     }
     return v;
 }
diff --git a/tests/experimental/liveness/liveness.slang.expected b/tests/experimental/liveness/liveness.slang.expected
index d8dcc1f62..77f14714e 100644
--- a/tests/experimental/liveness/liveness.slang.expected
+++ b/tests/experimental/liveness/liveness.slang.expected
@@ -7,7 +7,27 @@ standard output = {
 layout(row_major) uniform;
 layout(row_major) buffer;
 
-#line 24 0
+#line 85 0
+spirv_instruction(id = 256)
+void livenessStart_0(spirv_by_reference int _0, spirv_literal int _1);
+
+
+#line 85
+spirv_instruction(id = 256)
+void livenessStart_1(spirv_by_reference uint _0, spirv_literal int _1);
+
+
+#line 85
+spirv_instruction(id = 257)
+void livenessEnd_0(spirv_by_reference uint _0, spirv_literal int _1);
+
+
+#line 85
+spirv_instruction(id = 257)
+void livenessEnd_1(spirv_by_reference int _0, spirv_literal int _1);
+
+
+#line 24 1
 int someSlowFunc_0(int a_0)
 {
     uint _S1 = uint(a_0);
@@ -19,9 +39,15 @@ int someSlowFunc_0(int a_0)
     uint v_0;
 
 #line 26
+    livenessStart_0(i_0, 0);
+
+#line 26
     i_0 = 0;
 
 #line 26
+    livenessStart_1(v_0, 0);
+
+#line 26
     v_0 = _S1;
 
 #line 26
@@ -38,20 +64,53 @@ int someSlowFunc_0(int a_0)
         }
 
 #line 29
-        uint _S2 = uint(int(bool(v_0 >> 1) || bool(v_0 << 31)) * i_0);
+        uint _S2 = v_0 >> 1;
+
+#line 29
+        uint _S3 = v_0;
+
+#line 29
+        livenessEnd_0(v_0, 0);
+
+#line 29
+        uint _S4 = (_S2 | _S3 << 31) * uint(i_0);
+
+#line 27
+        int _S5 = i_0;
+
+#line 27
+        livenessEnd_1(i_0, 0);
+
+#line 27
+        int i_1 = _S5 + 1;
 
 #line 27
-        i_0 = i_0 + 1;
+        livenessStart_0(i_0, 0);
 
 #line 27
-        v_0 = _S2;
+        i_0 = i_1;
+
+#line 27
+        livenessStart_1(v_0, 0);
+
+#line 27
+        v_0 = _S4;
 
 #line 27
     }
 
+#line 27
+    livenessEnd_1(i_0, 0);
+
+#line 27
+    uint _S6 = v_0;
+
+#line 27
+    livenessEnd_0(v_0, 0);
+
 
 
-    return int(v_0);
+    return int(_S6);
 }
 
 
@@ -67,16 +126,16 @@ struct SomeStruct_0
 #line 17
 SomeStruct_0 makeSomeStruct_0()
 {
-    const int  _S3[100] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+    const int  _S7[100] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
 #line 19
-    SomeStruct_0 s_0 = { 0, 0, _S3 };
+    SomeStruct_0 s_0 = { 0, 0, _S7 };
     return s_0;
 }
 
 
 #line 15
-layout(std430, binding = 1) buffer _S4 {
+layout(std430, binding = 1) buffer _S8 {
     int _data[];
 } anotherBuffer_0;
 
@@ -96,18 +155,18 @@ int somethingElse_0(inout SomeStruct_0 s_2)
 
 
 #line 4
-layout(std430, binding = 0) buffer _S5 {
+layout(std430, binding = 0) buffer _S9 {
     int _data[];
 } outputBuffer_0;
 
 #line 4
 spirv_instruction(id = 256)
-void livenessStart_0(spirv_by_reference SomeStruct_0 _0, spirv_literal int _1);
+void livenessStart_2(spirv_by_reference SomeStruct_0 _0, spirv_literal int _1);
 
 
 #line 62
 spirv_instruction(id = 257)
-void livenessEnd_0(spirv_by_reference SomeStruct_0 _0, spirv_literal int _1);
+void livenessEnd_2(spirv_by_reference SomeStruct_0 _0, spirv_literal int _1);
 
 
 #line 46
@@ -119,13 +178,19 @@ void main()
     int index_0 = int(gl_GlobalInvocationID.x);
 
 #line 48
-    int i_1;
+    int i_2;
 
 #line 48
     int res_0;
 
 #line 48
-    i_1 = 0;
+    livenessStart_0(i_2, 0);
+
+#line 48
+    i_2 = 0;
+
+#line 48
+    livenessStart_0(res_0, 0);
 
 #line 48
     res_0 = index_0;
@@ -135,7 +200,7 @@ void main()
     {
 
 
-        if(i_1 < index_0)
+        if(i_2 < index_0)
         {
         }
         else
@@ -149,21 +214,21 @@ void main()
         SomeStruct_0 s_3;
 
 #line 56
-        livenessStart_0(s_3, 0);
+        livenessStart_2(s_3, 0);
         SomeStruct_0 t_0;
 
 #line 57
-        livenessStart_0(t_0, 0);
+        livenessStart_2(t_0, 0);
 
 #line 57
-        SomeStruct_0 _S6 = makeSomeStruct_0();
+        SomeStruct_0 _S10 = makeSomeStruct_0();
 
 #line 57
-        t_0 = _S6;
-        const int  _S7[100] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+        t_0 = _S10;
+        const int  _S11[100] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
 #line 58
-        SomeStruct_0 u_0 = { 0, 0, _S7 };
+        SomeStruct_0 u_0 = { 0, 0, _S11 };
 
 #line 58
         SomeStruct_0 u_1;
@@ -174,6 +239,9 @@ void main()
             t_0.x_0 = ((anotherBuffer_0)._data[(uint(v_1 & 3))]);
 
 #line 63
+            livenessStart_2(u_1, 0);
+
+#line 63
             u_1 = u_0;
 
 #line 63
@@ -185,18 +253,21 @@ void main()
             SomeStruct_0 x_1;
 
 #line 68
-            livenessStart_0(x_1, 0);
+            livenessStart_2(x_1, 0);
 
 #line 68
             x_1 = u_0;
             x_1.x_0 = ((anotherBuffer_0)._data[(uint(v_1 & 3))]) + 1;
-            SomeStruct_0 _S8 = x_1;
+            SomeStruct_0 _S12 = x_1;
 
 #line 70
-            livenessEnd_0(x_1, 0);
+            livenessEnd_2(x_1, 0);
 
 #line 70
-            u_1 = _S8;
+            livenessStart_2(u_1, 0);
+
+#line 70
+            u_1 = _S12;
 
 #line 70
         }
@@ -205,34 +276,67 @@ void main()
 
         s_3.c_0[index_0 & 7] = s_3.c_0[index_0 & 7] + 1;
 
-        int _S9 = s_3.x_0 + t_0.x_0 + u_1.x_0;
+        int _S13 = s_3.x_0 + t_0.x_0;
+
+#line 76
+        SomeStruct_0 _S14 = u_1;
+
+#line 76
+        livenessEnd_2(u_1, 0);
+
+#line 76
+        int _S15 = _S13 + _S14.x_0;
+
+#line 76
+        int _S16 = doThing_0(t_0);
+
+#line 76
+        int _S17 = _S15 + _S16;
 
 #line 76
-        int _S10 = doThing_0(t_0);
+        int _S18 = somethingElse_0(t_0);
 
 #line 76
-        int _S11 = _S9 + _S10;
+        livenessEnd_2(t_0, 0);
 
 #line 76
-        int _S12 = somethingElse_0(t_0);
+        int _S19 = _S17 + _S18;
 
 #line 76
-        livenessEnd_0(t_0, 0);
+        int _S20 = s_3.c_0[2];
 
 #line 76
-        int _S13 = _S11 + _S12;
+        livenessEnd_2(s_3, 0);
 
 #line 76
-        int _S14 = s_3.c_0[2];
+        int _S21 = _S19 + _S20;
 
 #line 76
-        livenessEnd_0(s_3, 0);
+        int _S22 = res_0;
 
 #line 76
-        int res_1 = res_0 + (_S13 + _S14);
+        livenessEnd_1(res_0, 0);
+
+#line 76
+        int res_1 = _S22 + _S21;
+
+#line 52
+        int _S23 = i_2;
+
+#line 52
+        livenessEnd_1(i_2, 0);
+
+#line 52
+        int i_3 = _S23 + 1;
+
+#line 52
+        livenessStart_0(i_2, 0);
+
+#line 52
+        i_2 = i_3;
 
 #line 52
-        i_1 = i_1 + 1;
+        livenessStart_0(res_0, 0);
 
 #line 52
         res_0 = res_1;
@@ -240,8 +344,17 @@ void main()
 #line 52
     }
 
+#line 52
+    livenessEnd_1(i_2, 0);
+
+#line 52
+    int _S24 = res_0;
+
+#line 52
+    livenessEnd_1(res_0, 0);
+
 #line 79
-    ((outputBuffer_0)._data[(uint(index_0))]) = res_0;
+    ((outputBuffer_0)._data[(uint(index_0))]) = _S24;
     return;
 }