Use IR pass to eliminate phi nodes (#2226)

* Use IR pass to eliminate phi nodes

"Phi nodes" are one of the key contrivances that makes SSA (Static
Single Assignment) form work. Because SSA is so great for compiler
IRs, we kind of need to deal with phi nodes, but they also get in
the way because they don't have a direct analog in most lower-level
machine ISAs or execution models, nor in most of the high-level
languages a transpiler wants to emit. As a result a compiler like
ours needs to be able to eliminate the phi nodes from a program as
part of generating output code.

(For any clever people noting that SPIR-V supports phi nodes
directly: yes, it does. It doesn't need to and it probably *shouldn't*.
Anybody involved in the decision-making knows my reasoning, and
anybody else should feel free to ask me if they want the lecture.
Anyway...)

The basic idea of elimiating phi nodes is simple enough. We replace
each phi node with a temporary variable. Uses of the phi use values
loaded from the temporary. The operation of the phi itself
(assigning a value based on the branch taken) amounts to an assignment
into the temporary.

Previously, the Slang compiler dealt with phi nodes very late in
the process of generating code: in the middle of emitting strings
of source code in a high-level language like HLSL or GLSL. Doing the
work that late in compilation has two big drawbacks:

1. Our ability to emit clean and/or optimal code is limited because
we may not be able to make certain changes to the IR, or because we
cannot make use of additional information like a dominator tree that
might be available at other points in compilation.

2. Any other IR passes that relate to temporary variables won't be
able to see the variables that we generate for phi nodes. This could
raise issues with correctness (e.g., if we want to compute live-range
information for *all* temporary variables), or performance (we have no
way to run additional IR optimization passes after phis are eliminated).

This change addresses these problems by making the elimination of
phi nodes an explicit IR pass. Additional optimizations can easily be
run after this pass (although we'd need to be careful not to run
passes that could end up introducing new phis). The pass makes use
of the information available to it to try to produce code that will
emit to "clean" HLSL/GLSL.

The core of the pass is in `slang-ir-eliminate-phis.cpp`, and is
heavily commented, so I won't describe the approach in detail here.
There are two related issues that came up, though:

First, it turned out that our emit logic for local variables (`IRVar`
instructions) wasn't using the function we'd defined named `emitVar()`.
One worrying consequence of that oversight was that the `precise`
modifier would impact generated HLSL/GLSL for variables that turned
into SSA values (including phi nodes), but *not* for local variables
that had not been SSA'd (or that had been SSA'd and then de-SSA'd).
This change also fixes that bug; it is unclear how widespread the
impact of the original issue might be.

Second, generating explicit IR temporaries for phi nodes exposed a
pre-existing bug in the `slang-ir-restructure-scoping` pass. That pass
basically detects cases where we have an instruction `I` with a use
`U` such that the use follows the rules of SSA form ("def dominates
use," meaning `I` dominations `U`), but does not follow the more
restrictive scoping rules of high-level-language output (where a value
computed "inside" a loop is not automatically visible to code outside
the loop just because it dominates that code). That pass did not
correctly account for the case where `I` was a temporary variable.
It seems that case could not arise before now because we didn't have
any passes that would move `var`, `load`, or `store` operations out
of the basic block they started in. The fix for that pass was relatively
simple, and will make the whole thing more robust in case we add more
aggressive optimizations later.

* fixup: expected test output

1 files changed, 82 insertions, 27 deletions

diff --git a/source/slang/slang-ir-restructure-scoping.cpp b/source/slang/slang-ir-restructure-scoping.cpp
index 0535483ec..dca1a92b6 100644
--- a/source/slang/slang-ir-restructure-scoping.cpp
+++ b/source/slang/slang-ir-restructure-scoping.cpp
@@ -307,24 +307,39 @@ static void fixValueScopingForInst(
         // If we've gotten this far, we know that `u` is a "bad"
         // use of `def`, and needs fixing.
         //
-        // We will create the `tmp` variable on demand, so
-        // that we create it when the first "bad" use is encountered,
-        // and then re-use it for subsequent bad uses.
+        // We will use a temporary variable to resolve the bad scoping,
+        // creating it on-demand when we ecounter a first "bad" use, and
+        // then re-using that temporary for any subsequent bad uses.
         //
         if( !tmp )
         {
-            // We will create a temporary to represent `def`,
-            // and insert a `store` into it right after `def`.
+            // If the value is *already* a temporary variable, then
+            // we are really just trying to fix the scoping of the
+            // variable declaration itself, and the variable can
+            // effectively be its own temporary.
             //
-            // Note: we are inserting the new variable right
-            // after `def` for now, just because we don't
-            // yet know the final region that it should be
-            // placed into. We will move it to the correct
-            // location when we are done.
-            //
-            builder.setInsertBefore(def->getNextInst());
-            tmp = builder.emitVar(def->getDataType());
-            builder.emitStore(tmp, def);
+            if(auto varDef = as<IRVar>(def))
+            {
+                tmp = varDef;
+            }
+            else
+            {
+                // We will create a temporary to represent `def`,
+                // and insert a `store` into it right after `def`.
+                //
+                // Note: we are inserting the new variable right
+                // after `def` for now, just because we don't
+                // yet know the final region that it should be
+                // placed into. We will move it to the correct
+                // location when we are done.
+                //
+                builder.setInsertBefore(def->getNextInst());
+                tmp = builder.emitVar(def->getDataType());
+                builder.emitStore(tmp, def);
+                //
+                // Note: the lifetime for the new variable starts
+                // right after the store we have emitted.
+            }
         }
 
         // In order to know where `tmp` should be defined
@@ -345,19 +360,40 @@ static void fixValueScopingForInst(
                 rr);
         }
 
-        // To fix up the use `u`, we will need to change
-        // it from using `def` to using a load from `tmp`
-        //
-        builder.setInsertBefore(user);
-        IRInst* tmpVal = builder.emitLoad(tmp);
-
-        // We are clobbering the value used by the `IRUse` `u`,
-        // while will cut it out of the list of uses for `def`.
-        // We need to be careful when doing this to not disrupt
-        // our iteration of the uses of `def`, so we carefully
-        // used the `nextUse` temporary at the start of the loop.
+        // We need to fix up the use `u`, but the way we fix
+        // it depends on whether we moving `def` itself (in which
+        // case `tmp` and `def` are the same), or if we have
+        // introduced an intermediate temporary.
         //
-        u->set(tmpVal);
+        if (def == tmp)
+        {
+            // If we are moving the definition itself, we don't
+            // need to do any kind of fix-up work at use sites.
+        }
+        else
+        {
+            // Othwerise we need to fix up the use `use` so
+            // that it uses a value loaded from `tmp` instead
+            // of `def`.
+            //
+            builder.setInsertBefore(user);
+            IRInst* tmpVal = builder.emitLoad(tmp);
+
+            // We are clobbering the value used by the `IRUse` `u`,
+            // while will cut it out of the list of uses for `def`.
+            // We need to be careful when doing this to not disrupt
+            // our iteration of the uses of `def`, so we carefully
+            // used the `nextUse` temporary at the start of the loop.
+            //
+            // Note(tfoley): This is more subtle than the comment makes
+            // it out to be, because we are *also* injecting a new use
+            // of `def` in the logic that creates `tmp` (because `def`
+            // is used as an operand to the `store` that initializes
+            // `tmp`). We really ought to work on a copy of the use-def
+            // information.
+            //
+            u->set(tmpVal);
+        }
     }
 
     // At the end of the loop, the `tmp` variable will have
@@ -421,8 +457,27 @@ void fixValueScoping(RegionTree* regionTree)
         if(!parentRegion)
             continue;
 
-        for(auto inst : block->getDecorationsAndChildren())
+        // Note: This pass will end up modifying the IR while also
+        // iterating over it. As such, we need to be careful not
+        // to let our iteration logic get confused.
+        //
+        // In particular, it is possible that `inst` will get moved
+        // to another block, as a way to resolve scoping issues, and
+        // if we did not account for that result, we might end up
+        // walking to the next instruction after `inst` even though
+        // it isn't inside `block`.
+        //
+        // We defensively cache the next instruction to visit so that
+        // we can continue our iteration after `inst` even if it gets
+        // moved. For now we are confident that the operations on
+        // `inst` won't affect `nextInst`, since the pass is not supposed
+        // to move or delete any *other* instructions.
+        //
+        IRInst* nextInst = nullptr;
+        for (auto inst = block->getFirstOrdinaryInst(); inst; inst = nextInst)
         {
+            nextInst = inst->getNextInst();
+
             fixValueScopingForInst(inst, parentRegion, regionTree);
         }
     }