From 1fef9b4abfce5ace686a6acc772c605503f825fd Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Sat, 3 Mar 2018 07:16:08 -0800 Subject: IR: next phase of "everything is an instruction" (#433) The main practical change here is that things that used to be `IRValue`s, like literals, are now being expressed as instructions in the global scope. In order to validate that things are actually being handled correctly, this change introduces an explicit "validation" pass that can be run on the IR to check for different invariants (although it doesn't check many of the important ones right now). I've left the validation pass turned off by default, but with a command-line flag to enable it. We may want to make it be on by default in debug builds, just to keep us honest. The main invariant for the moment is that when on IR instruction is used as an operand to another, it had better come from the same IR module. Some of the existing passes were violating this rule, in particular when it came to cloning of witness tables related to global generic parameter substitution. Those features can in theory be handled better now by allowing `specialize` instructions at other scopes, but I didn't want to over-complicate this change, so I make just enough fixes to ensure that these steps always clone witness tables they get from the "symbols" on an IR specialization context. In order for this to work when recursively specializing, I had to ensure that the logic for generic specialization had a notion of a "parent" specialization context that it would fall back to to perform cloning when necessary. This change keeps the logic that was caching and re-using the instructions for literal values within a module, but adds some logic that isn't really being tested right now for picking the right parent instruction to insert a constant instruction into. This logic doesn't trigger right now because all of the cases we are using it on have zero operands (and so they always get "hoisted" to the global scope), but eventually for things like types we want to be able to support instructions with operands (e.g., `vector`) and handle the case where some of those operands come from different scopes (e.g., when nested inside a generic). The final change here is mostly cosmetic: the `IRBuilder` is now more abstract about where insertion occurs: it tracks a single `IRParentInst` to insert into, and then an optional `IRInst` to insert before. In the common case, that parent is an `IRBlock`, but it could conceivably also be the global scope, or a witness table, etc. Use sites where we used to change those fields directly now use distinct methods `setInsertInto(parent)` and `setInsertBefore(inst)` which capture the two cases we care about. Accessors are also defined to extract the current block (if the current parent is a block), and the current "function" (global value with code, if the current parent is a global value with code, or a block inside one). With this work in place, it should be possible for a follow-on change to start putting `specialize` instructions at the global scope and thus clean up some of the on-the-fly specialization work. This work should also help with some of the requirements around a distinct IR-level type system and more explicit generics. --- source/slang/ir-validate.cpp | 182 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 182 insertions(+) create mode 100644 source/slang/ir-validate.cpp (limited to 'source/slang/ir-validate.cpp') diff --git a/source/slang/ir-validate.cpp b/source/slang/ir-validate.cpp new file mode 100644 index 000000000..95b8f2dff --- /dev/null +++ b/source/slang/ir-validate.cpp @@ -0,0 +1,182 @@ +// ir-validate.cpp +#include "ir-validate.h" + +#include "ir.h" +#include "ir-insts.h" + +namespace Slang +{ + struct IRValidateContext + { + // The IR module we are validating. + IRModule* module; + + // A diagnostic sink to send errors to if anything is invalid. + DiagnosticSink* sink; + + DiagnosticSink* getSink() { return sink; } + + // A set of instructions we've seen, to help confirm that + // values are defined before they are used in a given block. + HashSet seenInsts; + }; + + void validateIRInst( + IRValidateContext* context, + IRInst* inst); + + void validate(IRValidateContext* context, bool condition, IRInst* inst, char const* message) + { + if (!condition) + { + context->getSink()->diagnose(inst, Diagnostics::irValidationFailed, message); + } + } + + void validateIRInstChildren( + IRValidateContext* context, + IRParentInst* parent) + { + IRInst* prevChild = nullptr; + for (auto child = parent->getFirstChild(); child; child = child->getNextInst()) + { + // We need to check the integrity of the parent/next/prev links of + // all of our instructions + validate(context, child->parent == parent, child, "parent link"); + validate(context, child->prev == prevChild, child, "next/prev link"); + + // Recursively validate the instruction itself. + validateIRInst(context, child); + + prevChild = child; + } + } + + void validateIRInstOperand( + IRValidateContext* context, + IRInst* inst, + IRUse* operandUse) + { + // The `IRUse` for the operand had better have `inst` as its user. + validate(context, operandUse->getUser() == inst, inst, "operand user"); + + // The value we are using needs to fit into one of a few cases. + // + // * If the parent of `inst` and of `operand` is the same block, then + // we require that `operand` is defined before `inst` + // + // * If the parents of `inst` and `operand` are both blocks in the + // same functin, then the block defining `operand` must dominate + // the block defining `inst`. + // + // * Otherwise, we simply require that the parent of `operand` be + // an ancestor (transitive parent) of `inst`. + + auto instParent = inst->getParent(); + + auto operandValue = operandUse->get(); + auto operandParent = operandValue->getParent(); + + if (auto instParentBlock = as(instParent)) + { + if (auto operandParentBlock = as(operandParent)) + { + if (instParentBlock == operandParentBlock) + { + // If `operandValue` precedes `inst`, then we should + // have already seen it, because we scan parent instructions + // in order. + validate(context, context->seenInsts.Contains(operandValue), inst, "def must come before use in same block"); + return; + } + + auto instFunc = instParentBlock->getParent(); + auto operandFunc = operandParentBlock->getParent(); + if (instFunc == operandFunc) + { + // The two instructions are defined in different blocks of + // the same function (or another value with code). We need + // to validate that `operandParentBlock` dominates `instParentBlock`. + // + // TODO: implement this validation once we compute dominator trees. + // + // validate(context, operandParentBlock->dominates(instParentBlock), inst, "def must dominate use"); + return; + } + } + } + + // If the special cases above did not trigger, then either the two values + // are nested in the same parent, but that parent isn't a block, or they + // are nested in distinct parents, and those parents aren't both children + // of a function. + // + // In either case, we need to enforce that the parent of `operand` needs + // to be an ancestor of `inst`. + // + for (auto pp = instParent; pp; pp = pp->getParent()) + { + if (pp == operandParent) + return; + } + // + // We failed to find `operandParent` while walking the ancestors of `inst`, + // so something had gone wrong. + validate(context, false, inst, "def must be ancestor of use"); + } + + void validateIRInstOperands( + IRValidateContext* context, + IRInst* inst) + { + UInt operandCount = inst->getOperandCount(); + for (UInt ii = 0; ii < operandCount; ++ii) + { + validateIRInstOperand(context, inst, inst->getOperands() + ii); + } + } + + void validateIRInst( + IRValidateContext* context, + IRInst* inst) + { + // Validate that any operands of the instruction are used appropriately + validateIRInstOperands(context, inst); + context->seenInsts.Add(inst); + + // If `inst` is itself a parent instruction, then we need to recursively + // validate its children. + if (auto parent = as(inst)) + { + validateIRInstChildren(context, parent); + } + } + + void validateIRModule(IRModule* module, DiagnosticSink* sink) + { + IRValidateContext contextStorage; + IRValidateContext* context = &contextStorage; + context->module = module; + context->sink = sink; + + auto moduleInst = module->moduleInst; + + validate(context, moduleInst != nullptr, moduleInst, "module instruction"); + validate(context, moduleInst->parent == nullptr, moduleInst, "module instruction parent"); + validate(context, moduleInst->prev == nullptr, moduleInst, "module instruction prev"); + validate(context, moduleInst->next == nullptr, moduleInst, "module instruction next"); + + validateIRInst(context, module->moduleInst); + } + + void validateIRModuleIfEnabled( + CompileRequest* compileRequest, + IRModule* module) + { + if (!compileRequest->shouldValidateIR) + return; + + auto sink = &compileRequest->mSink; + validateIRModule(module, sink); + } +} -- cgit v1.2.3