Generate SSA form for IR functions (#400)

* Generate SSA form for IR functions

The basic idea here is simple: in the front-end after we have lowered the AST to initial IR we will apply a set of "mandatory" optimization passes. The first of these is to attempt to translate the all functions into SSA form so that they are amenable to subsequent dataflow optimizations. Eventually, the mandatory optimization passes would include diagnostic passes that make sure variables aren't used when undefined, etc.

Just doing basic SSA generation already cleans up a lot of the messiness in our IR today, because constructs that used to involve many local variables can now be handled via SSA temporaries.

The implementation of SSA generation is in `ir-ssa.cpp`, and it follows the approach of Braun et al.'s "Simple and Efficient Construction of Static Single Assignment Form." I used this instead of the more well-known Cytron et al. algorithm because Braun's algorith mis very simple to code, and does not require auxiliary analyses to generate the dominance frontier.

The main wrinkle in our SSA representation right now is that instead of using ordinary phi nodes, we instead allow basic blocks  to have parameters, where predecessor blocks pass in different parameter values. This encodes information equivalent to traditional phi nodes, but has two (small) benefits:

1. There is no fixed relationship between the order of phi operands and predecessor blocks, so we don't have to worry about breaking the phis when we alter the order in which predecessors are stored. This is important for us because predecessors are being stored implicitly.

2. It is easy to operationalize a "branch with arguments" either when lowering to other languages, or when interpreting the IR. A branch with arguments is implemented as a sequence of stores from the arguments to the parameters of the target block (very similar to a call), followed by a jump to the block.

Relevant to the above, this change also adds an interface for enumerating the predecessors or successors of a block in our CFG. Rather than use an auxliary structure, we directly use the information already encoded in the IR:

* The sucessors of a block are the target label operands of its terminator instruction. In our IR this is a contiguous range of `IRUse`s, possible with a stride (to account for the way `switch` interleaves values and blocks).

* The predecessors of a block are a subset of the uses of the block's value. Specifically, they are any uses that are on a terminator instruction, and within the range of values that represent the successor list of that instruction.

One important limitation of the "blocks with arguments" model for handling phis is that it is really only convenient to stash extra arguments on an unconditional terminator instruction. This change works around this prob lem by breaking any "critical edges" - edges between a block with multiple successors and one with multiple predecessors. We assume that "phi" nodes will only ever be needed on a block with multiple predecessors, and because critical edges are broken, each of these predecessors will then have only a single successor, so its branch instruction can handle the extra arguments.

This change introduces a notion of an "undefined" instruction in the IR. This is handled as an instruction rather than a value because I anticipate that we will want to distinguish different undefined values when it comes time to start issuing error messages (those messages will need to point to the variable that was used when undefined).

* Fix expected test output.

Another change was merged that enabled the `glsl-parameter-blocks` test, and its output is affected by our IR optimization work.

1 files changed, 257 insertions, 4 deletions

diff --git a/source/slang/ir.cpp b/source/slang/ir.cpp
index 77aac3f5a..634632f0d 100644
--- a/source/slang/ir.cpp
+++ b/source/slang/ir.cpp
@@ -28,16 +28,27 @@ namespace Slang
     {
         // TODO: need to make this faster by using a dictionary...
 
-        if (0) {}
+        static const struct {
+            char const* mnemonic;
+            IROp op;
+        } kOps[] = {
 
 #define INST(ID, MNEMONIC, ARG_COUNT, FLAGS)  \
-    else if(strcmp(name, #MNEMONIC) == 0) return kIROp_##ID;
+        { #MNEMONIC, kIROp_##ID },
 
 #define PSEUDO_INST(ID)  \
-    else if(strcmp(name, #ID) == 0) return kIRPseudoOp_##ID;
+        { #ID, kIRPseudoOp_##ID },
 
 #include "ir-inst-defs.h"
 
+        };
+
+        for (auto ee : kOps)
+        {
+            if (strcmp(name, ee.mnemonic) == 0)
+                return ee.op;
+        }
+
         return IROp(kIROp_Invalid);
     }
 
@@ -125,6 +136,228 @@ namespace Slang
         lastParam = param;
     }
 
+    // The predecessors of a block should all show up as users
+    // of its value, so rather than explicitly store the CFG,
+    // we will recover it on demand from the use-def information.
+    //
+    // Note: we are really iterating over incoming/outgoing *edges*
+    // for a block, because there might be multiple uses of a block,
+    // if more than one way of an N-way branch targets the same block.
+
+    // Get the list of successor blocks for an instruction,
+    // which we expect to be the last instruction in a block.
+    static IRBlock::SuccessorList getSuccessors(IRInst* terminator)
+    {
+        // If the block somehow isn't terminated, then
+        // there is no way to read its successors, so
+        // we return an empty list.
+        if (!terminator || !isTerminatorInst(terminator))
+            return IRBlock::SuccessorList(nullptr, nullptr);
+
+        // Otherwise, based on the opcode of the terminator
+        // instruction, we will build up our list of uses.
+        IRUse* begin = nullptr;
+        IRUse* end = nullptr;
+        UInt stride = 1;
+
+        auto args = terminator->getArgs();
+        switch (terminator->op)
+        {
+        case kIROp_ReturnVal:
+        case kIROp_ReturnVoid:
+        case kIROp_unreachable:
+        case kIROp_discard:
+            break;
+
+        case kIROp_unconditionalBranch:
+        case kIROp_break:
+        case kIROp_continue:
+        case kIROp_loop:
+            // unconditonalBranch <block>
+            begin = args + 0;
+            end = begin + 1;
+            break;
+
+        case kIROp_conditionalBranch:
+        case kIROp_if:
+        case kIROp_ifElse:
+        case kIROp_loopTest:
+            // conditionalBranch <condition> <trueBlock> <falseBlock>
+            begin = args + 1;
+            end = begin + 2;
+            break;
+
+        case kIROp_switch:
+            // switch <val> <break> <default> <caseVal1> <caseBlock1> ...
+            begin = args + 4;
+            end = args + terminator->getArgCount() + 1;
+            stride = 2;
+            break;
+
+        default:
+            assert(!"unepxected");
+            return IRBlock::SuccessorList(nullptr, nullptr);
+        }
+
+        return IRBlock::SuccessorList(begin, end, stride);
+    }
+
+    void IRBlock::insertAfter(IRBlock* other)
+    {
+        assert(other);
+        insertAfter(other, other->parentFunc);
+    }
+
+    void IRBlock::insertAfter(IRBlock* other, IRGlobalValueWithCode* func)
+    {
+        assert(other || func);
+
+        if (!other) other = func->lastBlock;
+        if (!func) func = other->parentFunc;
+
+        assert(func);
+
+        auto pp = other;
+        auto nn = other ? other->nextBlock : nullptr;
+
+        if (pp)
+        {
+            pp->nextBlock = this;
+        }
+        else
+        {
+            func->firstBlock = this;
+        }
+
+        if (nn)
+        {
+            nn->prevBlock = this;
+        }
+        else
+        {
+            func->lastBlock = this;
+        }
+
+        this->prevBlock = pp;
+        this->nextBlock = nn;
+        this->parentFunc = func;
+    }
+
+    static IRUse* adjustPredecessorUse(IRUse* use)
+    {
+        // We will search until we either find a
+        // suitable use, or run out of uses.
+        for (;use; use = use->nextUse)
+        {
+            // We only want to deal with uses that represent
+            // a "sucessor" operand to some terminator instruction.
+            // We will re-use the logic for getting the successor
+            // list from such an instruction.
+
+            auto successorList = getSuccessors((IRInst*) use->user);
+
+            if(use >= successorList.begin_
+                && use < successorList.end_)
+            {
+                UInt index = (use - successorList.begin_);
+                if ((index % successorList.stride) == 0)
+                {
+                    // This use is in the range of the sucessor list,
+                    // and so it represents a real edge between
+                    // blocks.
+                    return use;
+                }
+            }
+        }
+
+        // If we ran out of uses, then we are at the end
+        // of the list of incoming edges.
+        return nullptr;
+    }
+
+    IRBlock::PredecessorList IRBlock::getPredecessors()
+    {
+        // We want to iterate over the predecessors of this block.
+        // First, we resign ourselves to iterating over the
+        // incoming edges, rather than the blocks themselves.
+        // This might sound like a trival distinction, but it is
+        // possible for there to be multiple edges between two
+        // blocks (as for a `switch` with multiple cases that
+        // map to the same code). Any client that wants just
+        // the unique predecessor blocks needs to deal with
+        // the deduplication themselves.
+        //
+        // Next, we note that for any predecessor edge, there will
+        // be a use of this block in the terminator instruction of
+        // the predecessor. We basically just want to iterate over
+        // the users of this block, then, but we need to be careful
+        // to rule out anything that doesn't actually represent
+        // an edge. The `adjustPredecessorUse` function will be
+        // used to search for a use that actually represents an edge.
+
+        return PredecessorList(
+            adjustPredecessorUse(firstUse));
+    }
+
+    UInt IRBlock::PredecessorList::getCount()
+    {
+        UInt count = 0;
+        for (auto ii : *this)
+        {
+            (void)ii;
+            count++;
+        }
+        return count;
+    }
+
+    void IRBlock::PredecessorList::Iterator::operator++()
+    {
+        if (!use) return;
+        use = adjustPredecessorUse(use->nextUse);
+    }
+
+    IRBlock* IRBlock::PredecessorList::Iterator::operator*()
+    {
+        if (!use) return nullptr;
+        return (IRBlock*)use->user->parent;
+    }
+
+    IRBlock::SuccessorList IRBlock::getSuccessors()
+    {
+        // The successors of a block will all be listed
+        // as operands of its terminator instruction.
+        // Depending on the terminator, we might have
+        // different numbers of operands to deal with.
+        //
+        // (We might also have to deal with a "stride"
+        // in the case where the basic-block operands
+        // are mixed up with non-block operands)
+
+        auto terminator = getLastInst();
+        return Slang::getSuccessors(terminator);
+    }
+
+    UInt IRBlock::SuccessorList::getCount()
+    {
+        UInt count = 0;
+        for (auto ii : *this)
+        {
+            (void)ii;
+            count++;
+        }
+        return count;
+    }
+
+    void IRBlock::SuccessorList::Iterator::operator++()
+    {
+        use += stride;
+    }
+
+    IRBlock* IRBlock::SuccessorList::Iterator::operator*()
+    {
+        return (IRBlock*)use->usedValue;
+    }
+
     // IRFunc
 
     IRType* IRFunc::getResultType() { return getType()->getResultType(); }
@@ -609,6 +842,18 @@ namespace Slang
             &value);
     }
 
+    IRUndefined* IRBuilder::emitUndefined(IRType* type)
+    {
+        auto inst = createInst<IRUndefined>(
+            this,
+            kIROp_undefined,
+            type);
+
+        addInst(inst);
+    
+        return inst;
+    }
+
     IRValue* IRBuilder::getDeclRefVal(
         DeclRefBase const&  declRef)
     {
@@ -1004,13 +1249,20 @@ namespace Slang
         return bb;
     }
 
-    IRParam* IRBuilder::emitParam(
+    IRParam* IRBuilder::createParam(
         IRType* type)
     {
         auto param = createValue<IRParam>(
             this,
             kIROp_Param,
             type);
+        return param;
+    }
+
+    IRParam* IRBuilder::emitParam(
+        IRType* type)
+    {
+        auto param = createParam(type);
 
         if (auto bb = curBlock)
         {
@@ -3283,6 +3535,7 @@ namespace Slang
         case kIROp_Func:
         case kIROp_witness_table:
             return cloneGlobalValue(this, (IRGlobalValue*) originalValue);
+
         case kIROp_boolConst:
             {
                 IRConstant* c = (IRConstant*)originalValue;