Improve insertion location for "hoistable" instructions (#1593)

The Slang IR builder has a notion of "hoistable" instructions, which are basically those instructions that represent a pure side-effect-free operation on their operands, and which can and should be deduplicated. Most types are "hoistable" instructions.

In order to make deduplication of hoistable instructions work, we need to emit them at the right location. Consider if we had:

```hlsl
void myFunc<T>(...)
{
    if(someCondition) {
        vector<T, 4> a = ...;
        ...
    } else {
        vector<T, 4> b = ...;
    }
}
```

The IR instruction that represents `vector<T,4>` can't be inserted at the global scope, because then the parameter `T` would not be visible to it. That instruction also shouldn't be inserted into the same block that declares `a`, because then the instruction itself wouldn't be visible at the point where `b` is declared.

The IR builder already has logic to pick the right parent instruction. In the example given, the IR instruction for `vector<T,4>` should be inserted into the body of the IR generic, but outside of the IR function that represents `myFunc`.

The problem this change fixes is that while the logic was picking the *parent* for a hoistable instruction correctly, it wasn't putting much care into pick the insertion *location*. The existing strategy amounted to:

* If the IR builder was set with an insertion location inside the chosen parent, then use that insertion location

* Otherwise, insert at the end of the chosen parent

Neither of those options is perfect. Either could lead to an instruction being inserted after one of its uses, and the second option could even lead to a type being inserted *after* the `return` instruction in a function/generic, which violates another structural invariant of our IR (that every block must end with a terminator, and terminators must only appear at the end of blocks).

This change updates the rules as follows:

* If the type of the instruction being created, or any of its operands are in the chosen parent, then insert immediately after whichever of those instructions is last in that parent.

* Otherwise, insert before the first non-decoration, non-parameter child of the chosen parent

The combined effect of these two rules is now that we insert any hoistable instruction as early as we can in its parent, without violating the structural validity rules.

(One small exception to these rules is that if the parent is the module then we don't worry about ordering and just insert at the end, since order-of-declaration isn't significant at module scope in our IR)

All of our existing tests work with this new behavior, although there could conceivably be future cases that lead to complicated breakage. For example, if a pass looks at the first "ordinary" instruction in a block and saves it to use as an insertion point for parameter, and then proceeds to manipulate code in the block before going back and inserting parameters at the chosen location, there is a chance that a hoistable instruction might have been inserted before the chosen insertion point, leading to a parameter being inserted after an ordinary instruction. In general, though, code that works like that would already be playing a dangerous game in that it is manipulating instructions in a block while assuming the first instruction will remain fixed.

This change is currently just a refactor, but the underlying issue surfaced as a bug when I made other changes in a feature branch.

2 files changed, 210 insertions, 12 deletions

diff --git a/source/slang/slang-ir-validate.cpp b/source/slang/slang-ir-validate.cpp
index 15228200e..94f0da047 100644
--- a/source/slang/slang-ir-validate.cpp
+++ b/source/slang/slang-ir-validate.cpp
@@ -37,6 +37,23 @@ namespace Slang
         IRValidateContext*  context,
         IRInst*             parent)
     {
+        // We want to check that child instructions are correctly
+        // ordered so that decorations come first, then any parameters,
+        // and then any ordinary instructions.
+        //
+        // We will track what we have seen so far with a simple state
+        // machine, which in valid IR should proceed monitonically
+        // up through the following states:
+        //
+        enum State
+        {
+            kState_Initial = 0,
+            kState_AfterDecoration,
+            kState_AfterParam,
+            kState_AfterOrdinary,
+        };
+        State state = kState_Initial;
+
         IRInst* prevChild = nullptr;
         for(auto child : parent->getDecorationsAndChildren() )
         {
@@ -48,6 +65,21 @@ namespace Slang
             // Recursively validate the instruction itself.
             validateIRInst(context, child);
 
+            if( as<IRDecoration>(child) )
+            {
+                validate(context, state <= kState_AfterDecoration, child, "decorations must come before other child instructions");
+                state = kState_AfterDecoration;
+            }
+            else if( as<IRParam>(child) )
+            {
+                validate(context, state <= kState_AfterParam, child, "parameters must come before ordinary instructions");
+                state = kState_AfterParam;
+            }
+            else
+            {
+                state = kState_AfterOrdinary;
+            }
+
             // Do some extra validation around terminator instructions:
             //
             // * The last instruction of a block should always be a terminator
diff --git a/source/slang/slang-ir.cpp b/source/slang/slang-ir.cpp
index dc106fff1..30790af84 100644
--- a/source/slang/slang-ir.cpp
+++ b/source/slang/slang-ir.cpp
@@ -1328,6 +1328,89 @@ namespace Slang
         return inst;
     }
 
+        /// Return whichever of `left` or `right` represents the later point in a common parent
+    static IRInst* pickLaterInstInSameParent(
+        IRInst* left,
+        IRInst* right)
+    {
+        // When using instructions to represent insertion locations,
+        // a null instruction represents the end of the parent block,
+        // so if either of the two instructions is null, it indicates
+        // the end of the parent, and thus comes later.
+        //
+        if(!left) return nullptr;
+        if(!right) return nullptr;
+
+        // In the non-null case, we must have the precondition that
+        // the two candidates have the same parent.
+        //
+        SLANG_ASSERT(left->getParent() == right->getParent());
+
+        // No matter what, figuring out which instruction comes first
+        // is a linear-time operation in the number of instructions
+        // in the same parent, but we can optimize based on the
+        // assumption that in common cases one of the following will
+        // hold:
+        //
+        // * `left` and `right` are close to one another in the IR
+        // * `left` and/or `right` is close to the start of its parent
+        //
+        // To optimize for those conditions, we create two cursors that
+        // start at `left` and `right` respectively, and scan backward.
+        //
+        auto ll = left;
+        auto rr = right;
+        for(;;)
+        {
+            // If one of the cursors runs into the other while scanning
+            // backwards, then it implies it must have been the later
+            // of the two.
+            //
+            // This is our early-exit condition for `left` and `right`
+            // being close together.
+            //
+            // Note: this condition will trigger on the first iteration
+            // in the case where `left == right`.
+            //
+            if(ll == right) return left;
+            if(rr == left)  return right;
+
+            // If one of the cursors reaches the start of the block,
+            // then that implies it started at the earlier position.
+            // In that case, the other candidate must be the later
+            // one.
+            //
+            // This is the early-exit condition for `left` and/or `right`
+            // being close to the start of the parent.
+            //
+            if(!ll) return right;
+            if(!rr) return left;
+
+            // Otherwise, we move both cursors backward and continue
+            // the search.
+            //
+            ll = ll->getPrevInst();
+            rr = rr->getPrevInst();
+
+            // Note: in the worst case, one of the cursors is
+            // at the end of the parent, and the other is halfway
+            // through, so that each cursor needs to visit half
+            // of the instructions in the parent before we reach
+            // one of our termination conditions.
+            //
+            // As a result the worst-case running time is still O(N),
+            // and there is nothing we can do to improve that
+            // with our linked-list representation.
+            //
+            // If the assumptions given turn out to be wrong, and
+            // we find that a common case is instructions close
+            // to the *end* of a block, we can either flip the
+            // direction that the cursors traverse, or even add
+            // two more cursors that scan forward instead of
+            // backward.
+        }
+    }
+
     // Given an instruction that represents a constant, a type, etc.
     // Try to "hoist" it as far toward the global scope as possible
     // to insert it at a location where it will be maximally visible.
@@ -1359,23 +1442,106 @@ namespace Slang
             parent = mergeCandidateParentsForHoistableInst(parent, operandParent);
         }
 
-        // We better have ended up with a place to insert.
+        // We better have ended up with a parent to insert into,
+        // or else the invariants of our IR have been violated.
+        //
         SLANG_ASSERT(parent);
 
-        // If we have chosen to insert into the same parent that the
-        // IRBuilder is configured to use, then respect its `insertBeforeInst`
-        // setting.
-        if (parent == builder->insertIntoParent)
-        {
-            builder->addInst(inst);
-            return;
-        }
+        // Once we determine the parent instruction that the
+        // new instruction should be inserted into, we need
+        // to find an appropriate place to insert it.
+        //
+        // There are two concerns at play here, both of which
+        // stem from the property that within a block we
+        // require definitions to precede their uses.
+        //
+        // The first concern is that we want to emit a
+        // "hoistable" instruction like a type as early as possible,
+        // so that if a subsequent optimization pass requests
+        // the same type/value again, it doesn't get a cached/deduplicated
+        // pointer to an instruction that comes after the code being
+        // processed.
+        //
+        // The second concern is that we must emit any hoistable
+        // instruction after any of its operands (or its type)
+        // if they come from the same block/parent.
+        //
+        // These two conditions together indicate that we want
+        // to insert the instruction right after whichever of
+        // its operands come last in the parent block and if
+        // none of the operands come from the same block, we
+        // should try to insert it as early as possible in
+        // that block.
+        //
+        // We want to insert a hoistable instruction at the
+        // earliest possible point in its parent, which
+        // should be right after whichever of its operands
+        // is defined in that same block (if any)
+        //
+        // We will solve this problem by computing the
+        // earliest instruction that it would be valid for
+        // us to insert before.
+        //
+        // We start by considering insertion before the
+        // first instruction in the parent (if any) and
+        // then move the insertion point later as needed.
+        //
+        // Note: a null `insertBeforeInst` is used
+        // here to mean to insert at the end of the parent.
+        //
+        IRInst* insertBeforeInst = parent->getFirstChild();
 
-        // Otherwise, we just want to insert at the end of the chosen parent.
+        // Hoistable instructions are always "ordinary"
+        // instructions, so they need to come after
+        // any parameters of the parent.
         //
-        // TODO: be careful about inserting after the terminator of a block...
+        while(auto param = as<IRParam>(insertBeforeInst))
+            insertBeforeInst = param->getNextInst();
+
+        // For instructions that will be placed at module scope,
+        // we don't care about relative ordering, but for everything
+        // else, we want to ensure that an instruction comes after
+        // its type and operands.
+        //
+        if( !as<IRModuleInst>(parent) )
+        {
+            // We need to make sure that if any of
+            // the operands of `inst` come from the same
+            // block that we insert after them.
+            //
+            for (UInt ii = 0; ii < operandCount; ++ii)
+            {
+                auto operand = inst->getOperand(ii);
+                if (!operand)
+                    continue;
+
+                if(operand->getParent() != parent)
+                    continue;
+
+                insertBeforeInst = pickLaterInstInSameParent(insertBeforeInst, operand->getNextInst());
+            }
+            //
+            // Similarly, if the type of `inst` comes from
+            // the same parent, then we need to make sure
+            // we insert after the type.
+            //
+            if(auto type = inst->getFullType())
+            {
+                if(type->getParent() == parent)
+                {
+                    insertBeforeInst = pickLaterInstInSameParent(insertBeforeInst, type->getNextInst());
+                }
+            }
+        }
 
-        inst->insertAtEnd(parent);
+        if( insertBeforeInst )
+        {
+            inst->insertBefore(insertBeforeInst);
+        }
+        else
+        {
+            inst->insertAtEnd(parent);
+        }
     }
 
     static void maybeSetSourceLoc(