IR: overhaul IR design/implementation (#195)

* IR: overhaul IR design/implementation

Closes #192
Closes #188

This is a major overhaul of how the IR is implemented, with the primary goal of just using the AST-level type representation as the IR's type representation, rather than inventing an entire shadow set of types (as captured in issue #192).
One consequence of this choice is that types in the IR are no longer explicit "instructions" and are not represented as ordinary operands (so a bunch of `+ 1` cases end up going away when enumerating ordinary operands).

Along the way I also got rid of the embedded IDs in the IR (issue #188) because this wasn't too hard to deal with at the same time.

Another related change was to split the `IRValue` and `IRInst` cases, so that there are values that are not also instructions. Non-instruction values are now used to represent literals, references to declarations, and would eventually be used for an `undef` value if we need one. IR functions, global variables, and basic blocks are all values (because they can appear as operands), but not instructions.

The main benefit of this approach is that the top-level structure of a bytecode (BC) module is much simpler to understand and walk, and BC-level types are represented much more directly (such that we could conceivably use them for reflection soon).

* fixup: 64-bit build fix

* fixup: try to silence clang's pedantic dependent-type errors

* fixup: bug in VM loading of constants

1 files changed, 126 insertions, 135 deletions

diff --git a/source/slang/ir.h b/source/slang/ir.h
index 9c3124478..7e4dc8f83 100644
--- a/source/slang/ir.h
+++ b/source/slang/ir.h
@@ -11,36 +11,14 @@
 
 namespace Slang {
 
-// TODO(tfoley): We should ditch this enumeration
-// and just use the IR opcodes that represent these
-// types directly. The one major complication there
-// is that the order of the enum values currently
-// matters, since it determines promotion rank.
-// We either need to keep that restriction, or
-// look up promotion rank by some other means.
-//
-enum class BaseType
-{
-    // Note(tfoley): These are ordered in terms of promotion rank, so be vareful when messing with this
-
-    Void = 0,
-    Bool,
-    Int,
-    UInt,
-    UInt64,
-    Half,
-    Float,
-    Double,
-};
-
+class   FuncType;
+class   Layout;
+class   Type;
 
-class Layout;
-
-struct IRFunc;
-struct IRInst;
-struct IRModule;
-struct IRParentInst;
-struct IRType;
+struct  IRFunc;
+struct  IRInst;
+struct  IRModule;
+struct  IRValue;
 
 typedef unsigned int IROpFlags;
 enum : IROpFlags
@@ -75,34 +53,6 @@ enum IROp : int16_t
 
 };
 
-#if 0
-enum IRPseudoOp
-{
-    kIRPseudoOp_Pos         = -1000,
-    kIRPseudoOp_PreInc,
-    kIRPseudoOp_PreDec,
-    kIRPseudoOp_PostInc,
-    kIRPseudoOp_PostDec,
-    kIRPseudoOp_Sequence,
-    kIRPseudoOp_AddAssign,
-    kIRPseudoOp_SubAssign,
-    kIRPseudoOp_MulAssign,
-    kIRPseudoOp_DivAssign,
-    kIRPseudoOp_ModAssign,
-    kIRPseudoOp_AndAssign,
-    kIRPseudoOp_OrAssign,
-    kIRPseudoOp_XorAssign ,
-    kIRPseudoOp_LshAssign,
-    kIRPseudoOp_RshAssign,
-    kIRPseudoOp_Assign,
-    kIRPseudoOp_BitNot,
-    kIRPseudoOp_And,
-    kIRPseudoOp_Or,
-
-    kIROp_Invalid = -1,
-};
-#endif
-
 IROp findIROp(char const* name);
 
 // A logical operation/opcode in the IR
@@ -125,12 +75,12 @@ IROpInfo getIROpInfo(IROp op);
 // A use of another value/inst within an IR operation
 struct IRUse
 {
+    // The value that is being used
+    IRValue* usedValue;
+
     // The value that is doing the using.
     IRInst* user;
 
-    // The value that is being used
-    IRInst* usedValue;
-
     // The next use of the same value
     IRUse*  nextUse;
 
@@ -138,7 +88,7 @@ struct IRUse
     // so that we can simplify updates.
     IRUse** prevLink;
 
-    void init(IRInst* user, IRInst* usedValue);
+    void init(IRInst* user, IRValue* usedValue);
 };
 
 enum IRDecorationOp : uint16_t
@@ -162,52 +112,61 @@ struct IRDecoration
     IRDecorationOp op;
 };
 
-typedef uint32_t IRInstID;
+// Use AST-level types directly to represent the
+// types of IR instructions/values
+typedef Type IRType;
+
+struct IRBlock;
 
-// In the IR, almost *everything* is an instruction,
-// in order to make the representation as uniform as possible.
-struct IRInst
+// Base class for values in the IR
+struct IRValue
 {
     // The operation that this value represents
     IROp op;
 
-    // A unique ID to represent the op when printing
-    // (or zero to indicate that the value of this
-    // op isn't special).
-    IRInstID id;
+    // 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 arguments of this instruction
-    // (including the type)
-    uint32_t argCount;
-
-    // The parent of this instruction.
-    // This will often be a basic block, but we
-    // allow instructions to nest in more general ways.
-    IRParentInst*    parent;
-
-    // The next and previous instructions in the same parent block
-    IRInst*     nextInst;
-    IRInst*     prevInst;
+    Type* getType() { return type; }
 
-    // The first use of this value (start of a linked list)
-    IRUse*      firstUse;
-
-    // The linked list of decorations attached to this instruction
+    // The linked list of decorations attached to this value
     IRDecoration* firstDecoration;
 
+    // Look up a decoration in the list of decorations
     IRDecoration* findDecorationImpl(IRDecorationOp op);
-
     template<typename T>
     T* findDecoration()
     {
         return (T*) findDecorationImpl(IRDecorationOp(T::kDecorationOp));
     }
 
+    // The first use of this value (start of a linked list)
+    IRUse*      firstUse;
 
-    // The type of this value
-    IRUse       type;
 
-    IRType* getType() { return (IRType*) type.usedValue; }
+};
+
+// Instructions are values that can be executed,
+// and which take other values as operands
+struct IRInst : IRValue
+{
+    // 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;
+
+    // The basic block that contains this instruction.
+    IRBlock*    parentBlock;
+
+    // The next and previous instructions in the same parent block
+    IRInst*     nextInst;
+    IRInst*     prevInst;
 
     UInt getArgCount()
     {
@@ -216,20 +175,16 @@ struct IRInst
 
     IRUse*      getArgs();
 
-    IRInst* getArg(UInt index)
+    IRValue* getArg(UInt index)
     {
         return getArgs()[index].usedValue;
     }
 };
 
-// This type alias exists because I waffled on the name for a bit.
-// All existing uses of `IRValue` should move to `IRInst`
-typedef IRInst IRValue;
-
 typedef int64_t IRIntegerValue;
 typedef double IRFloatingPointValue;
 
-struct IRConstant : IRInst
+struct IRConstant : IRValue
 {
     union
     {
@@ -241,16 +196,6 @@ struct IRConstant : IRInst
     } u;
 };
 
-// Representation of a type at the IR level.
-// Such a type may not correspond to the high-level-language notion
-// of a type as used by the front end.
-//
-// Note that types are instructions in the IR, so that operations
-// may take type operands as easily as values.
-struct IRType : IRInst
-{
-};
-
 // A instruction that ends a basic block (usually because of control flow)
 struct IRTerminatorInst : IRInst
 {};
@@ -258,23 +203,20 @@ struct IRTerminatorInst : IRInst
 bool isTerminatorInst(IROp op);
 bool isTerminatorInst(IRInst* inst);
 
-
-// A parent instruction contains a sequence of other instructions
+// A function parameter is owned by a basic block, and represents
+// either an incoming function parameter (in the entry block), or
+// a value that flows from one SSA block to another (in a non-entry
+// block).
 //
-struct IRParentInst : IRInst
+// In each case, the basic idea is that a block is a "label with
+// arguments."
+struct IRParam : IRValue
 {
-    // The first and last instruction in the container (or NULL in
-    // the case that the container is empty).
-    //
-    IRInst* firstChild;
-    IRInst* lastChild;
-};
+    IRParam*    nextParam;
+    IRParam*    prevParam;
 
-// A function parameter is represented by an instruction
-// in the entry block of a function.
-struct IRParam : IRInst
-{
-    IRParam* getNextParam();
+    IRParam* getNextParam() { return nextParam; }
+    IRParam* getPrevParam() { return prevParam; }
 };
 
 // A basic block is a parent instruction that adds the constraint
@@ -282,48 +224,97 @@ struct IRParam : IRInst
 // no function declarations, or nested blocks). We also expect
 // that the previous/next instruction are always a basic block.
 //
-struct IRBlock : IRParentInst
+struct IRBlock : IRValue
 {
+    // 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 `last` should actually be an `IRTerminatorInst`.
+    // and `lastInst` should actually be an `IRTerminatorInst`.
+    IRInst* firstInst;
+    IRInst* lastInst;
 
-    IRBlock* getPrevBlock() { return (IRBlock*) prevInst; }
-    IRBlock* getNextBlock() { return (IRBlock*) nextInst; }
+    IRInst* getFirstInst() { return firstInst; }
+    IRInst* getLastInst() { return lastInst; }
 
-    IRFunc* getParent() { return (IRFunc*)parent; }
+    // 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;
+
+    IRParam* getFirstParam() { return firstParam; }
+    IRParam* getLastParam() { return lastParam; }
+    void addParam(IRParam* param);
+
+    // The parent function that contains this block
+    IRFunc* parentFunc;
+
+    IRFunc* getParent() { return parentFunc; }
 
-    IRParam* getFirstParam();
 };
 
-struct IRFuncType;
+// For right now, we will represent the type of
+// an IR function using the type of the AST
+// function from which it was created.
+//
+// TODO: need to do this better.
+typedef FuncType IRFuncType;
+
+struct IRGlobalValue : IRValue
+{};
 
 // A function is a parent to zero or more blocks of instructions.
 //
 // A function is itself a value, so that it can be a direct operand of
 // an instruction (e.g., a call).
-struct IRFunc : IRParentInst
+struct IRFunc : IRGlobalValue
 {
-    IRFuncType* getType() { return (IRFuncType*) type.usedValue; }
+    // The type of the IR-level function
+    IRFuncType* getType() { return (IRFuncType*) type.Ptr(); }
+
+    // The mangled name, for a function
+    // that should have linkage.
+    String mangledName;
 
-    IRType* getResultType();
+    // Convenience accessors for working with the 
+    // function's type.
+    Type* getResultType();
     UInt getParamCount();
-    IRType* getParamType(UInt index);
+    Type* getParamType(UInt index);
 
-    IRBlock* getFirstBlock() { return (IRBlock*) firstChild; }
-    IRBlock* getLastBlock() { return (IRBlock*) lastChild; }
+    // The list of basic blocks in this function
+    IRBlock*    firstBlock = nullptr;
+    IRBlock*    lastBlock = nullptr;
 
+    IRBlock* getFirstBlock() { return firstBlock; }
+    IRBlock* getLastBlock() { return lastBlock; }
+
+    // Add a block to the end of this function.
+    void addBlock(IRBlock* block);
+
+    // Convenience accessor for the IR parameters,
+    // which are actually the parameters of the first
+    // block.
     IRParam* getFirstParam();
 };
 
 // A module is a parent to functions, global variables, types, etc.
-struct IRModule : IRParentInst
+struct IRModule : RefObject
 {
     // The designated entry-point function, if any
     IRFunc*     entryPoint;
 
-    // A special counter used to assign logical ids to instructions in this module.
-    IRInstID    idCounter;
+    // A list of all the functions and other
+    // global values declared in this module.
+    List<IRGlobalValue*> globalValues;
+
+    // TODO: need a symbol of all the global variables too
 };
 
 void printSlangIRAssembly(StringBuilder& builder, IRModule* module);