diff options
Diffstat (limited to 'source/slang/ir.h')
| -rw-r--r-- | source/slang/ir.h | 463 |
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() { |