IR: "everything is an instruction" (#432)

* IR: "everything is an instruction"

This change tries to streamline the representation of the IR in the following ways:

* Every IR value is an instruction (there is no `IRValue` type any more)

* All IR values that can contain other values share a single base (`IRParentInstruction`)

* Dynamic casts to specific IR instruction types can be accomplished with a new `as<Type>(inst)` operation, that uses the IR opcode to implement casts.

The biggest change in terms of number of lines is getting rid of `IRValue`. The diff here could probably be smaller if I'd just done `typedef IRInst IRValue;`.

Along the way I also renamed the `getArg`/`getArgs`/`getArgCount` combination over to `getOperand`/`getOperands`/`getOperandCount` to avoid being confusing when we have something like a `call` instruction where the "arguments" of the call don't line up with the operands of the instruction.

I also tried to clean up the representation of lists of child instructions to try to make it easier to iterate over them with C++ range-based `for` loops. Developers still need to be careful about mutating the contents of a block while iterating over it in this fashion (e.g. if you remove the "current" element, the iteration will end prematurely).

Probably the thorniest change here is that parameters are now just represented as the first N instructions in a block, which means:

* We need to perform a linear search to find the end of the parameter list. This is probably not often a problem, because usually you would be iterating over the parameters anyway, and that will be linear in the number of parameters.

* Algorithms that iterate over a block either need to ignore parameters, treat parameters just like other instructions, or somehow cleave the list into the range of parameters, and the range of "ordinary" instructions (which involves the same linear search above).

* When inserting into a block, we need to be careful not to insert instructions at invalid locations (e.g., insert a temporary before the parameters, or insert a parameter in the middle of the code). I can't pretend that I've handled the details of that here. (This is no different than having to make the same adjustments for phi nodes in a typical SSA representation)

  * One possible future-proof approach is to implement a pass that sorts the instructions in a block so that parameters always come first. That would let us implement passes without caring about this detail, and then clean up right before any pass that cares about the relative order of parameters and other instructions.

The current change is missing any work to make literals and other instructions that used to be `IRValue`s properly nest inside of their parent module. Right now these instructions are just left unparented, and may actually end up being shared between distinct modules. Fixing that will need a follow-up change. The biggest challenge there is that it introduces instructions at the global scope that aren't `IRGlobalValue`s.

This change doesn't try to take advantage of any of the new flexibility (e.g., by nesting `specialize` instructions inside of witness tables). The goal is to do exactly what we were doing before, just with a different  representation.

* Warning fix

1 files changed, 284 insertions, 179 deletions

diff --git a/source/slang/ir.h b/source/slang/ir.h
index 8f350827a..95a7a97d1 100644
--- a/source/slang/ir.h
+++ b/source/slang/ir.h
@@ -25,8 +25,6 @@ struct  IRFunc;
 struct  IRGlobalValueWithCode;
 struct  IRInst;
 struct  IRModule;
-struct  IRUser;
-struct  IRValue;
 
 typedef unsigned int IROpFlags;
 enum : IROpFlags
@@ -57,6 +55,13 @@ enum IROp : int16_t
 
 #include "ir-inst-defs.h"
 
+#define INST(ID, MNEMONIC, ARG_COUNT, FLAGS) /* empty */
+#define INST_RANGE(BASE, FIRST, LAST)       \
+    kIROp_First##BASE   = kIROp_##FIRST,    \
+    kIROp_Last##BASE    = kIROp_##LAST,
+
+#include "ir-inst-defs.h"
+
     kIROp_Invalid = -1,
 
 };
@@ -83,18 +88,18 @@ IROpInfo getIROpInfo(IROp op);
 // A use of another value/inst within an IR operation
 struct IRUse
 {
-    IRValue* get() { return usedValue; }
-    IRUser* getUser() { return user; }
+    IRInst* get() { return usedValue; }
+    IRInst* getUser() { return user; }
 
-    void init(IRUser* user, IRValue* usedValue);
-    void set(IRValue* usedValue);
+    void init(IRInst* user, IRInst* usedValue);
+    void set(IRInst* usedValue);
     void clear();
 
-    // The value that is being used
-    IRValue* usedValue = nullptr;
+    // The instruction that is being used
+    IRInst* usedValue = nullptr;
 
-    // The value that is doing the using.
-    IRUser* user = nullptr;
+    // The instruction that is doing the using.
+    IRInst* user = nullptr;
 
     // The next use of the same value
     IRUse*  nextUse = nullptr;
@@ -145,22 +150,30 @@ struct IRDecoration : public IRObject
 typedef Type IRType;
 
 struct IRBlock;
+struct IRParentInst;
 
-// Base class for values in the IR
-struct IRValue : public IRObject
+// Every value in the IR is an instruction (even things
+// like literal values).
+//
+struct IRInst : public IRObject
 {
     // The operation that this value represents
     IROp op;
 
-    // The type of the result value of this instruction,
-    // or `null` to indicate that the instruction has
-    // no value.
-    RefPtr<Type>    type;
+    // The total number of operands of this instruction.
+    //
+    // TODO: We shouldn't need to allocate this on
+    // all instructions. Instead we should have
+    // instructions that need "vararg" support to
+    // allocate this field ahead of the `this`
+    // pointer.
+    uint32_t operandCount = 0;
 
-    Type* getFullType() { return type; }
+    UInt getOperandCount()
+    {
+        return operandCount;
+    }
 
-    Type* getRate();
-    Type* getDataType();
 
     // Source location information for this value, if any
     SourceLoc sourceLoc;
@@ -180,154 +193,196 @@ struct IRValue : public IRObject
     IRUse*      firstUse = nullptr;
 
 
+    // The parent of this instruction.
+    IRParentInst*   parent;
+
+    IRParentInst* getParent() { return parent; }
+
+    // The next and previous instructions with the same parent
+    IRInst*         next;
+    IRInst*         prev;
+
+    IRInst* getNextInst() { return next; }
+    IRInst* getPrevInst() { return prev; }
+
+    // The type of the result value of this instruction,
+    // or `null` to indicate that the instruction has
+    // no value.
+    RefPtr<Type>    type;
+
+    Type* getFullType() { return type; }
+
+    Type* getRate();
+    Type* getDataType();
+
+    // After the type, we have data that is specific to
+    // the subtype of `IRInst`. In most cases, this is
+    // just a series of `IRUse` values representing
+    // operands of the instruction.
+
+    IRUse*      getOperands();
+
+    IRInst* getOperand(UInt index)
+    {
+        return getOperands()[index].get();
+    }
+
+    void setOperand(UInt index, IRInst* value)
+    {
+        getOperands()[index].set(value);
+    }
+
+
+    //
+
     // Replace all uses of this value with `other`, so
     // that this value will now have no uses.
-    void replaceUsesWith(IRValue* other);
+    void replaceUsesWith(IRInst* other);
 
     // Free a value (which needs to have been removed
     // from its parent, had its uses eliminated, etc.)
     void deallocate();
 
+    // Clean up any non-pool resources used by this instruction
     virtual void dispose() override;
-};
 
-// Values that are contained in a doubly-linked
-// list inside of some parent.
-//
-// TODO: consider merging this into `IRValue` so
-// that *all* values have a parent.
-struct IRChildValue : IRValue
-{
-    // The parent of this value.
-    IRValue*        parent;
+    // Insert this instruction into the same basic block
+    // as `other`, right before/after it.
+    void insertBefore(IRInst* other);
+    void insertAfter(IRInst* other);
+
+    // Insert as first/last child of given parent
+    void insertAtStart(IRParentInst* parent);
+    void insertAtEnd(IRParentInst* parent);
+
+    // Move to the start/end of current parent
+    void moveToStart();
+    void moveToEnd();
+
+    // Insert before/after the given instruction, in a specific block
+    void insertBefore(IRInst* other, IRParentInst* parent);
+    void insertAfter(IRInst* other, IRParentInst* parent);
+
+    // Remove this instruction from its parent block,
+    // but don't delete it, or replace uses.
+    void removeFromParent();
+
+    // Remove this instruction from its parent block,
+    // and then destroy it (it had better have no uses!)
+    void removeAndDeallocate();
+
+    // Clear out the arguments of this instruction,
+    // so that we don't appear on the list of uses
+    // for those values.
+    void removeArguments();
 
-    // The next and previous values in the same
-    // list on teh same parent.
-    IRChildValue*   next;
-    IRChildValue*   prev;
 };
 
-// Helper for storing linked lists of child values.
-struct IRValueListBase
+// `dynamic_cast` equivalent
+template<typename T>
+T* as(IRInst* inst, T* /* */ = nullptr)
 {
-    IRChildValue* first = 0;
-    IRChildValue* last = 0;
+    if (inst && T::isaImpl(inst->op))
+        return (T*) inst;
+    return nullptr;
+}
 
-protected:
-    void addImpl(IRValue* parent, IRChildValue* val);
-};
+// `static_cast` equivalent, with debug validation
 template<typename T>
-struct IRValueList : IRValueListBase
+T* cast(IRInst* inst, T* /* */ = nullptr)
 {
-    T* getFirst() { return (T*)first; }
-    T* getLast() { return (T*)last; }
+    SLANG_ASSERT(!inst || as<T>(inst));
+    return (T*)inst;
+}
+
+
+// A double-linked list of instruction
+struct IRInstListBase
+{
+    IRInstListBase()
+    {}
+
+    IRInstListBase(IRInst* first, IRInst* last)
+        : first(first)
+        , last(last)
+    {}
+
 
-    void add(IRValue* parent, T* val)
-    {
-        addImpl(parent, val);
-    }
+
+    IRInst* first = 0;
+    IRInst* last = 0;
+
+    IRInst* getFirst() { return first; }
+    IRInst* getLast() { return last; }
 
     struct Iterator
     {
-        T* val;
+        IRInst* inst;
 
-        Iterator() : val(0) {}
-        Iterator(T* val) : val(val) {}
+        Iterator() : inst(nullptr) {}
+        Iterator(IRInst* inst) : inst(inst) {}
 
         void operator++()
         {
-            if (val)
+            if (inst)
             {
-                val = (T*)val->next;
+                inst = inst->next;
             }
         }
 
-        T* operator*()
+        IRInst* operator*()
         {
-            return val;
+            return inst;
         }
 
         bool operator!=(Iterator const& i)
         {
-            return val != i.val;
+            return inst != i.inst;
         }
     };
 
-    Iterator begin() { return Iterator(getFirst()); }
-    Iterator end() { return Iterator(nullptr); }
+    Iterator begin() { return Iterator(first); }
+    Iterator end() { return Iterator(last ? last->next : nullptr); }
 };
 
-// Values that can use other values. These always
-// have their operands "tail allocated" after
-// the fields of this type, so derived types must
-// either:
-//
-// - Add no new fields, or
-// - Add only fields that represent the `IRUse` operands
-// - Add a fixed number of `IRUse` operand fields and
-//   then any additional data after them.
-//
-struct IRUser : IRChildValue
+// Specialization of `IRInstListBase` for the case where
+// we know (or at least expect) all of the instructions
+// to be of type `T`
+template<typename T>
+struct IRInstList : IRInstListBase
 {
-    // The total number of arguments of this instruction.
-    //
-    // TODO: We shouldn't need to allocate this on
-    // all instructions. Instead we should have
-    // instructions that need "vararg" support to
-    // allocate this field ahead of the `this`
-    // pointer.
-    uint32_t argCount = 0;
+    IRInstList() {}
 
-    UInt getArgCount()
-    {
-        return argCount;
-    }
+    IRInstList(T* first, T* last)
+        : IRInstListBase(first, last)
+    {}
 
-    IRUse*      getArgs();
+    explicit IRInstList(IRInstListBase const& list)
+        : IRInstListBase(list)
+    {}
 
-    IRValue* getArg(UInt index)
-    {
-        return getArgs()[index].get();
-    }
+    T* getFirst() { return (T*) first; }
+    T* getLast() { return (T*) last; }
 
-    void setArg(UInt index, IRValue* value)
+    struct Iterator : public IRInstListBase::Iterator
     {
-        getArgs()[index].set(value);
-    }
-};
-
-// Instructions are values that are children of a basic block,
-// and can actually be executed.
-struct IRInst : IRUser
-{
-    IRBlock* getParentBlock() { return (IRBlock*)parent; }
+        Iterator() {}
+        Iterator(IRInst* inst) : IRInstListBase::Iterator(inst) {}
 
-    IRInst* getPrevInst() { return (IRInst*)prev; }
-    IRInst* getNextInst() { return (IRInst*)next; }
-
-
-    // Insert this instruction into the same basic block
-    // as `other`, right before it.
-    void insertBefore(IRInst* other);
-
-    // Remove this instruction from its parent block,
-    // but don't delete it, or replace uses.
-    void removeFromParent();
-
-    // Remove this instruction from its parent block,
-    // and then destroy it (it had better have no uses!)
-    void removeAndDeallocate();
+        T* operator*()
+        {
+            return (T*) inst;
+        }
+    };
 
-    // Clear out the arguments of this instruction,
-    // so that we don't appear on the list of uses
-    // for those values.
-    void removeArguments();
+    Iterator begin() { return Iterator(first); }
+    Iterator end() { return Iterator(last ? last->next : nullptr); }
 };
 
 typedef int64_t IRIntegerValue;
 typedef double IRFloatingPointValue;
 
-struct IRConstant : IRValue
+struct IRConstant : IRInst
 {
     union
     {
@@ -341,10 +396,12 @@ struct IRConstant : IRValue
 
 // A instruction that ends a basic block (usually because of control flow)
 struct IRTerminatorInst : IRInst
-{};
-
-bool isTerminatorInst(IROp op);
-bool isTerminatorInst(IRInst* inst);
+{
+    static bool isaImpl(IROp op)
+    {
+        return (op >= kIROp_FirstTerminatorInst) && (op <= kIROp_LastTerminatorInst);
+    }
+};
 
 // A function parameter is owned by a basic block, and represents
 // either an incoming function parameter (in the entry block), or
@@ -354,15 +411,26 @@ bool isTerminatorInst(IRInst* inst);
 // In each case, the basic idea is that a block is a "label with
 // arguments."
 //
-// Note: an `IRParam` is an `IRUser` *just* so that we can use
-// it as the user of other values during SSA generation.
-struct IRParam : IRUser
+struct IRParam : IRInst
+{
+    IRParam* getNextParam();
+    IRParam* getPrevParam();
+
+    static bool isaImpl(IROp op) { return op == kIROp_Param; }
+};
+
+// A "parent" instruction is one that contains other instructions
+// as its children. The most common case of a parent instruction
+// is a basic block, but there are other cases (e.g., a function
+// is in turn a parent for basic blocks).
+struct IRParentInst : IRInst
 {
-    IRParam*    nextParam;
-    IRParam*    prevParam;
+    // The instructions stored under this parent
+    IRInstListBase children;
 
-    IRParam* getNextParam() { return nextParam; }
-    IRParam* getPrevParam() { return prevParam; }
+    IRInst* getFirstChild() { return children.first; }
+    IRInst* getLastChild()  { return children.last;  }
+    IRInstListBase getChildren() { return children; }
 };
 
 // A basic block is a parent instruction that adds the constraint
@@ -370,42 +438,63 @@ struct IRParam : IRUser
 // no function declarations, or nested blocks). We also expect
 // that the previous/next instruction are always a basic block.
 //
-struct IRBlock : IRValue
+struct IRBlock : IRParentInst
 {
     // Linked list of the instructions contained in this block
     //
-    // Note that in a valid program, every block must end with
-    // a "terminator" instruction, so these should be non-NULL,
-    // and `lastInst` should actually be an `IRTerminatorInst`.
-    IRInst* firstInst;
-    IRInst* lastInst;
+    IRInstListBase getChildren() { return children; }
+    IRInst* getFirstInst() { return children.first; }
+    IRInst* getLastInst() { return children.last; }
 
-    IRInst* getFirstInst() { return firstInst; }
-    IRInst* getLastInst() { return lastInst; }
-
-    // Links for the list of basic blocks in the parent function
-    IRBlock* prevBlock;
-    IRBlock* nextBlock;
-
-    IRBlock* getPrevBlock() { return prevBlock; }
-    IRBlock* getNextBlock() { return nextBlock; }
-
-    // Linked list of parameters of this block
-    IRParam* firstParam;
-    IRParam* lastParam;
+    // In a valid program, every basic block should end with
+    // a "terminator" instruction.
+    //
+    // This function will return the terminator, if it exists,
+    // or `null` if there is none.
+    IRTerminatorInst* getTerminator() { return as<IRTerminatorInst>(getLastInst()); }
+
+    // We expect that the siblings of a basic block will
+    // always be other basic blocks (we don't allow
+    // mixing of blocks and other instructions in the
+    // same parent).
+    IRBlock* getPrevBlock() { return cast<IRBlock>(getPrevInst()); }
+    IRBlock* getNextBlock() { return cast<IRBlock>(getNextInst()); }
+
+    // The parameters of a block are represented by `IRParam`
+    // instructions at the start of the block. These play
+    // the role of function parameters for the entry block
+    // of a function, and of phi nodes in other blocks.
+    IRParam* getFirstParam() { return as<IRParam>(getFirstInst()); }
+    IRParam* getLastParam();
+    IRInstList<IRParam> getParams()
+    {
+        return IRInstList<IRParam>(
+            getFirstParam(),
+            getLastParam());
+    }
 
-    IRParam* getFirstParam() { return firstParam; }
-    IRParam* getLastParam() { return lastParam; }
     void addParam(IRParam* param);
 
-    // The parent function that contains this block
-    IRGlobalValueWithCode* parentFunc;
-
-    IRGlobalValueWithCode* getParent() { return parentFunc; }
-
-    void insertAfter(IRBlock* other);
-    void insertAfter(IRBlock* other, IRGlobalValueWithCode* func);
-
+    // The parent of a basic block is assumed to be a
+    // value with code (e.g., a function, global variable
+    // with initializer, etc.).
+    IRGlobalValueWithCode* getParent() { return cast<IRGlobalValueWithCode>(IRInst::getParent()); }
+
+    // The predecessor and successor lists of a block are needed
+    // when we want to work with the control flow graph (CFG) of
+    // a function. Rather than store these explicitly (and thus
+    // need to update them when transformations might change the
+    // CFG), we compute predecessors and successors in an
+    // implicit fashion using the use-def information for a
+    // block itself.
+    //
+    // To a first approximation, the predecessors of a block
+    // are the blocks where the IR value of the block is used.
+    // Similarly, the successors of a block are all values used
+    // by the terminator instruction of the block.
+    // The `getPredecessors()` and `getSuccessors()` functions
+    // make this more precise.
+    // 
     struct PredecessorList
     {
         PredecessorList(IRUse* begin) : b(begin) {}
@@ -465,6 +554,10 @@ struct IRBlock : IRValue
 
     PredecessorList getPredecessors();
     SuccessorList getSuccessors();
+
+    //
+
+    static bool isaImpl(IROp op) { return op == kIROp_Block; }
 };
 
 // For right now, we will represent the type of
@@ -474,21 +567,17 @@ struct IRBlock : IRValue
 // TODO: need to do this better.
 typedef FuncType IRFuncType;
 
-struct IRGlobalValue : IRValue
+// A "global value" is an instruction that might have
+// linkage, so that it can be declared in one module
+// and then resolved to a definition in another module.
+struct IRGlobalValue : IRParentInst
 {
-    IRModule*   parentModule;
-
     // The mangled name, for a symbol that should have linkage,
     // or which might have multiple declarations.
     Name* mangledName = nullptr;
 
-
-    IRGlobalValue*  nextGlobalValue;
-    IRGlobalValue*  prevGlobalValue;
-
-    IRGlobalValue*  getNextValue() { return nextGlobalValue; }
-    IRGlobalValue*  getPrevValue() { return prevGlobalValue; }
-
+#if 0
+    // TODO: these all belong on `IRInst`
     void insertBefore(IRGlobalValue* other);
     void insertBefore(IRGlobalValue* other, IRModule* module);
     void insertAtStart(IRModule* module);
@@ -500,18 +589,26 @@ struct IRGlobalValue : IRValue
     void removeFromParent();
 
     void moveToEnd();
+#endif
+
+    static bool isaImpl(IROp op)
+    {
+        return (op >= kIROp_FirstGlobalValue) && (op <= kIROp_LastGlobalValue);
+    }
 };
 
 /// @brief A global value that potentially holds executable code.
 ///
 struct IRGlobalValueWithCode : IRGlobalValue
 {
-    // The list of basic blocks in this function
-    IRBlock*    firstBlock = nullptr;
-    IRBlock*    lastBlock = nullptr;
-
-    IRBlock* getFirstBlock() { return firstBlock; }
-    IRBlock* getLastBlock() { return lastBlock; }
+    // The children of a value with code will be the basic
+    // blocks of its definition.
+    IRBlock* getFirstBlock() { return cast<IRBlock>(getFirstChild()); }
+    IRBlock* getLastBlock() { return cast<IRBlock>(getLastChild()); }
+    IRInstList<IRBlock> getBlocks()
+    {
+        return IRInstList<IRBlock>(getChildren());
+    }
 
     // Add a block to the end of this function.
     void addBlock(IRBlock* block);
@@ -557,7 +654,18 @@ struct IRFunc : IRGlobalValueWithCode
     }
 };
 
-// A module is a parent to functions, global variables, types, etc.
+// The IR module itself is represented as an instruction, which
+// serves at the root of the tree of all instructions in the module.
+struct IRModuleInst : IRParentInst
+{
+    // Pointer back to the non-instruction object that represents
+    // the module, so that we can get back to it in algorithms
+    // that need it.
+    IRModule* module;
+
+    IRInstListBase getGlobalInsts() { return getChildren(); }
+};
+
 struct IRModule : RefObject
 {
     // The compilation session in use.
@@ -565,13 +673,10 @@ struct IRModule : RefObject
     MemoryPool  memoryPool;
     List<IRObject*> irObjectsToFree; // list of ir objects to run destructor upon destruction
 
-    // A list of all the functions and other
-    // global values declared in this module.
-    IRGlobalValue*  firstGlobalValue = nullptr;
-    IRGlobalValue*  lastGlobalValue = nullptr;
+    IRModuleInst* moduleInst;
+    IRModuleInst* getModuleInst() { return moduleInst;  }
 
-    IRGlobalValue*  getFirstGlobalValue() { return firstGlobalValue; }
-    IRGlobalValue*  getlastGlobalValue() { return lastGlobalValue; }
+    IRInstListBase getGlobalInsts() { return getModuleInst()->getChildren(); }
 
     ~IRModule()
     {