diff options
| -rw-r--r-- | source/slang/check.cpp | 54 | ||||
| -rw-r--r-- | source/slang/diagnostic-defs.h | 2 | ||||
| -rw-r--r-- | source/slang/emit.cpp | 618 | ||||
| -rw-r--r-- | source/slang/ir-legalize-types.cpp | 2 | ||||
| -rw-r--r-- | source/slang/ir-restructure-scoping.cpp | 434 | ||||
| -rw-r--r-- | source/slang/ir-restructure-scoping.h | 24 | ||||
| -rw-r--r-- | source/slang/ir-restructure.cpp | 662 | ||||
| -rw-r--r-- | source/slang/ir-restructure.h | 261 | ||||
| -rw-r--r-- | source/slang/ir.cpp | 29 | ||||
| -rw-r--r-- | source/slang/ir.h | 10 | ||||
| -rw-r--r-- | source/slang/slang.vcxproj | 4 | ||||
| -rw-r--r-- | source/slang/slang.vcxproj.filters | 10 | ||||
| -rw-r--r-- | tests/bugs/gh-569.slang | 36 | ||||
| -rw-r--r-- | tests/bugs/gh-569.slang.expected.txt | 4 | ||||
| -rw-r--r-- | tests/compute/multiple-continue-sites.slang | 39 | ||||
| -rw-r--r-- | tests/compute/multiple-continue-sites.slang.expected.txt | 4 | ||||
| -rw-r--r-- | tools/render-test/d3d-util.cpp | 1 |
17 files changed, 1749 insertions, 445 deletions
diff --git a/source/slang/check.cpp b/source/slang/check.cpp index 67c747861..19e349807 100644 --- a/source/slang/check.cpp +++ b/source/slang/check.cpp @@ -131,30 +131,58 @@ namespace Slang } bool fromOperatorExpr(OperatorExpr* opExpr) { + // First, lets see if the argument types are ones + // that we can encode in our space of keys. args[0].aggVal = 0; args[1].aggVal = 0; if (opExpr->Arguments.Count() > 2) return false; + + for (UInt i = 0; i < opExpr->Arguments.Count(); i++) + { + if (!args[i].fromType(opExpr->Arguments[i]->type.Ptr())) + return false; + } + + // Next, lets see if we can find an intrinsic opcode + // attached to an overloaded definition (filtered for + // definitions that could conceivably apply to us). + // + // TODO: This should really be pased on the operator name + // plus fixity, rather than the intrinsic opcode... + // + // We will need to reject postfix definitions for prefix + // operators, and vice versa, to ensure things work. + // + auto prefixExpr = opExpr->As<PrefixExpr>(); + auto postfixExpr = opExpr->As<PostfixExpr>(); + if (auto overloadedBase = opExpr->FunctionExpr->As<OverloadedExpr>()) { - Decl* funcDecl = overloadedBase->lookupResult2.item.declRef.decl; - if (auto genDecl = funcDecl->As<GenericDecl>()) - funcDecl = genDecl->inner.Ptr(); - if (auto intrinsicOp = funcDecl->FindModifier<IntrinsicOpModifier>()) + for(auto item : overloadedBase->lookupResult2 ) { - operatorName = intrinsicOp->op; - for (UInt i = 0; i < opExpr->Arguments.Count(); i++) + // Look at a candidate definition to be called and + // see if it gives us a key to work with. + // + Decl* funcDecl = overloadedBase->lookupResult2.item.declRef.decl; + if (auto genDecl = funcDecl->As<GenericDecl>()) + funcDecl = genDecl->inner.Ptr(); + + // Reject definitions that have the wrong fixity. + // + if(prefixExpr && !funcDecl->FindModifier<PrefixModifier>()) + continue; + if(postfixExpr && !funcDecl->FindModifier<PostfixModifier>()) + continue; + + if (auto intrinsicOp = funcDecl->FindModifier<IntrinsicOpModifier>()) { - if (!args[i].fromType(opExpr->Arguments[i]->type.Ptr())) - return false; + operatorName = intrinsicOp->op; + return true; } } - else - { - return false; - } } - return true; + return false; } }; diff --git a/source/slang/diagnostic-defs.h b/source/slang/diagnostic-defs.h index f8e048bdb..f531ae851 100644 --- a/source/slang/diagnostic-defs.h +++ b/source/slang/diagnostic-defs.h @@ -352,6 +352,8 @@ DIAGNOSTIC(51090, Error, cannotGenerateCodeForExternComponentType, "cannot gener DIAGNOSTIC(51091, Error, typeCannotBePlacedInATexture, "type '$0' cannot be placed in a texture.") DIAGNOSTIC(51092, Error, stageDoesntHaveInputWorld, "'$0' doesn't appear to have any input world"); +DIAGNOSTIC(52000, Error, multiLevelBreakUnsupported, "control flow appears to require multi-level `break`, which Slang does not yet support"); + // 99999 - Internal compiler errors, and not-yet-classified diagnostics. diff --git a/source/slang/emit.cpp b/source/slang/emit.cpp index a6460bf10..3e601e119 100644 --- a/source/slang/emit.cpp +++ b/source/slang/emit.cpp @@ -2,6 +2,8 @@ #include "emit.h" #include "ir-insts.h" +#include "ir-restructure.h" +#include "ir-restructure-scoping.h" #include "ir-ssa.h" #include "ir-validate.h" #include "legalize-types.h" @@ -144,12 +146,16 @@ struct SharedEmitContext // Map an IR instruction to the name that we've decided // to use for it when emitting code. Dictionary<IRInst*, String> mapInstToName; + + DiagnosticSink* getSink() { return &entryPoint->compileRequest->mSink; } }; struct EmitContext { // The shared context that is in effect SharedEmitContext* shared; + + DiagnosticSink* getSink() { return shared->getSink(); } }; // @@ -3340,14 +3346,7 @@ struct EmitVisitor case kIROp_Not: { - if (as<IRBoolType>(inst->getDataType())) - { - emit("!"); - } - else - { - emit("~"); - } + emit("!"); emitIROperand(ctx, inst->getOperand(0), mode); } break; @@ -3360,7 +3359,14 @@ struct EmitVisitor break; case kIROp_BitNot: { - emit("~"); + if (as<IRBoolType>(inst->getDataType())) + { + emit("!"); + } + else + { + emit("~"); + } emitIROperand(ctx, inst->getOperand(0), mode); } break; @@ -3776,203 +3782,173 @@ struct EmitVisitor } } - enum LabelOp - { - kLabelOp_break, - kLabelOp_continue, - - kLabelOpCount, - }; - - struct LabelStack - { - LabelStack* parent; - IRBlock* block; - LabelOp op; - }; - - // We want to emit a range of code in the IR, represented - // by the blocks that are logically in the interval [begin, end) - // which we consider as a single-entry multiple-exit region. - // - // Note: because there are multiple exists, control flow - // may exit this region with operations that do *not* branch - // to `end`, but such non-local control flow will hopefully - // be captured. - // - void emitIRStmtsForBlocks( + /// Emit high-level language statements from a structrured region. + void emitRegion( EmitContext* ctx, - IRBlock* begin, - IRBlock* end, - - // Labels to use at the start - LabelStack* initialLabels, - - // Labels to switch to after emitting first basic block - LabelStack* labels = nullptr) + Region* inRegion) { - if(!labels) - labels = initialLabels; - - auto useLabels = initialLabels; - - IRBlock* block = begin; - while(block != end) + // We will use a loop so that we can process sequential (simple) + // regions iteratively rather than recursively. + // This is effectively an emulation of tail recursion. + Region* region = inRegion; + while(region) { - // If the block we are trying to emit has been registered as a - // destination label (e.g. for a loop or `switch`) then we - // may need to emit a `break` or `continue` as needed. - // - // TODO: we eventually need to handle the possibility of - // multi-level break/continue targets, which could be challenging. - - // First, figure out which block has been registered as - // the current `break` and `continue` target. - IRBlock* registeredBlock[kLabelOpCount] = {}; - for( auto ll = labels; ll; ll = ll->parent ) - { - if(!registeredBlock[ll->op]) - { - registeredBlock[ll->op] = ll->block; - } - } - - // Next, search in the active labels we are allowed to use, - // and see if the block we are trying to branch to is an - // available break/continue target. - for(auto ll = useLabels; ll; ll = ll->parent) + // What flavor of region are we trying to emit? + switch(region->getFlavor()) { - if(ll->block == block) + case Region::Flavor::Simple: { - // We are trying to go to a block that has been regsitered as a label. + // A simple region consists of a basic block followed + // by another region. + // + auto simpleRegion = (SimpleRegion*) region; - if(block != registeredBlock[ll->op]) + // We start by outputting all of the non-terminator + // instructions in the block. + // + auto block = simpleRegion->block; + auto terminator = block->getTerminator(); + for (auto inst = block->getFirstInst(); inst != terminator; inst = inst->getNextInst()) { - // ERROR: need support for multi-level break/continue to pull this one off! + emitIRInst(ctx, inst, IREmitMode::Default); } - switch(ll->op) + // Next we have to deal with the terminator instruction + // itself. In many cases, the terminator will have been + // turned into a block of its own, but certain cases + // of terminators are simple enough that we just fold + // them into the current block. + // + advanceToSourceLocation(terminator->sourceLoc); + switch(terminator->op) { - case kLabelOp_break: - emit("break;\n"); + default: + // Don't do anything with the terminator, and assume + // its behavior has been folded into the next region. break; - case kLabelOp_continue: - emit("continue;\n"); + case kIROp_ReturnVal: + case kIROp_ReturnVoid: + case kIROp_discard: + // For extremely simple terminators, we just handle + // them here, so that we don't have to allocate + // separate `Region`s for them. + emitIRInst(ctx, terminator, IREmitMode::Default); break; - } - - return; - } - } - // Start by emitting the non-terminator instructions in the block. - auto terminator = block->getLastInst(); - SLANG_ASSERT(as<IRTerminatorInst>(terminator)); - for (auto inst = block->getFirstInst(); inst != terminator; inst = inst->getNextInst()) - { - emitIRInst(ctx, inst, IREmitMode::Default); - } - - // Now look at the terminator instruction, which will tell us what we need to emit next. - - advanceToSourceLocation(terminator->sourceLoc); + // We will also handle any unconditional branches + // here, since they may have arguments to pass + // to the target block (our encoding of SSA + // "phi" operations). + // + // TODO: A better approach would be to move out of SSA + // as an IR pass, and introduce explicit variables to + // replace any "phi nodes." This would avoid possible + // complications if we ever end up in the bad case where + // one of the block arguments on a branch is also + // a paremter of the target block, so that the order + // of operations is important. + // + case kIROp_unconditionalBranch: + { + auto t = (IRUnconditionalBranch*)terminator; + UInt argCount = t->getOperandCount(); + static const UInt kFixedArgCount = 1; + emitPhiVarAssignments( + ctx, + argCount - kFixedArgCount, + t->getOperands() + kFixedArgCount, + t->getTargetBlock()); + } + break; + case kIROp_loop: + { + auto t = (IRLoop*) terminator; + UInt argCount = t->getOperandCount(); + static const UInt kFixedArgCount = 3; + emitPhiVarAssignments( + ctx, + argCount - kFixedArgCount, + t->getOperands() + kFixedArgCount, + t->getTargetBlock()); - switch (terminator->op) - { - default: - SLANG_UNEXPECTED("terminator inst"); - return; + } + break; + } - case kIROp_unreachable: - return; + // If the terminator required a full region to represent + // its behavior in a structured form, then we will move + // along to that region now. + // + // We do this iteratively rather than recursively, by + // jumping back to the top of our loop with a new + // value for `region`. + // + region = simpleRegion->nextRegion; + continue; + } - case kIROp_ReturnVal: - case kIROp_ReturnVoid: - case kIROp_discard: - emitIRInst(ctx, terminator, IREmitMode::Default); - return; + // Break and continue regions are trivial to handle, as long as we + // don't need to consider multi-level break/continue (which we + // don't for now). + case Region::Flavor::Break: + emit("break;\n"); + break; + case Region::Flavor::Continue: + emit("continue;\n"); + break; - case kIROp_ifElse: + case Region::Flavor::If: { - // Two-sided `if` statement - auto t = (IRIfElse*)terminator; - - auto trueBlock = t->getTrueBlock(); - auto falseBlock = t->getFalseBlock(); - auto afterBlock = t->getAfterBlock(); + auto ifRegion = (IfRegion*) region; // TODO: consider simplifying the code in - // the case where `trueBlock == afterBlock` - // so that we output `if(!cond) { falseBlock }` - // instead of the current `if(cond) {} else {falseBlock}` + // the case where `ifRegion == null` + // so that we output `if(!condition) { elseRegion }` + // instead of the current `if(condition) {} else { elseRegion }` emit("if("); - emitIROperand(ctx, t->getCondition(), IREmitMode::Default); + emitIROperand(ctx, ifRegion->condition, IREmitMode::Default); emit(")\n{\n"); indent(); - emitIRStmtsForBlocks( - ctx, - trueBlock, - afterBlock, - labels); + emitRegion(ctx, ifRegion->thenRegion); dedent(); emit("}\n"); - // Don't emit the false block if it would be empty - if(falseBlock != afterBlock) + + // Don't emit the `else` region if it would be empty + // + if(auto elseRegion = ifRegion->elseRegion) { emit("else\n{\n"); indent(); - emitIRStmtsForBlocks( - ctx, - falseBlock, - afterBlock, - labels); + emitRegion(ctx, elseRegion); dedent(); emit("}\n"); } - // Continue with the block after the `if` - block = afterBlock; + // Continue with the region after the `if`. + // + // TODO: consider just constructing a `SimpleRegion` + // around an `IfRegion` to handle this sequencing, + // rather than making `IfRegion` serve as both a + // conditional and a sequence. + // + region = ifRegion->nextRegion; + continue; } break; - case kIROp_loop: + case Region::Flavor::Loop: { - // Header for a `while` or `for` loop - auto t = (IRLoop*)terminator; - - auto targetBlock = t->getTargetBlock(); - auto breakBlock = t->getBreakBlock(); - - UInt argCount = t->getOperandCount(); - static const UInt kFixedArgCount = 3; - emitPhiVarAssignments( - ctx, - argCount - kFixedArgCount, - t->getOperands() + kFixedArgCount, - targetBlock); - - // Set up entries on our label stack for break/continue - - LabelStack subBreakLabel; - subBreakLabel.parent = labels; - subBreakLabel.block = breakBlock; - subBreakLabel.op = kLabelOp_break; - - // Note: when forming the `continue` label, we don't - // actually point at the "continue block" from the loop - // statement, because we aren't actually going to - // generate an ordinary continue caluse in a `for` loop. + auto loopRegion = (LoopRegion*) region; + auto loopInst = loopRegion->loopInst; + + // If the user applied an explicit decoration to the loop, + // to control its unrolling behavior, then pass that + // along in the output code (if the target language + // supports the semantics of the decoration). // - // Instead, our `continue` label will always be the - // loop header. - LabelStack subContinueLabel; - subContinueLabel.parent = &subBreakLabel; - subContinueLabel.block = targetBlock; - subContinueLabel.op = kLabelOp_continue; - - if (auto loopControlDecoration = t->findDecoration<IRLoopControlDecoration>()) + if (auto loopControlDecoration = loopInst->findDecoration<IRLoopControlDecoration>()) { switch (loopControlDecoration->mode) { @@ -3991,289 +3967,67 @@ struct EmitVisitor emit("for(;;)\n{\n"); indent(); - emitIRStmtsForBlocks( - ctx, - targetBlock, - nullptr, - // For the first block, we only want the `break` label active - &subBreakLabel, - // After the first block, we can safely use the `continue` label too - &subContinueLabel); + emitRegion(ctx, loopRegion->body); dedent(); emit("}\n"); - // Continue with the block after the loop - block = breakBlock; - } - break; - -#if 0 - case kIROp_break: - { - auto t = (IRBreak*)terminator; - auto targetBlock = t->getTargetBlock(); - - UInt argCount = t->getArgCount(); - static const UInt kFixedArgCount = 1; - emitPhiVarAssignments( - ctx, - argCount - kFixedArgCount, - t->getArgs() + kFixedArgCount, - targetBlock); - - emit("break;\n"); - } - return; - - case kIROp_continue: - // With out current strategy for outputting loops, - // just outputting an AST-level `continue` here won't - // actually execute the statements in the continue block. - // - // Instead, we have to manually output those statements - // directly here, and *then* do an AST-level `continue`. - // - // This leads to code duplication when we have multiple - // `continue` sites in the original program, but it avoids - // introducing additional temporaries for control flow. - { - auto continueInst = (IRContinue*) terminator; - auto targetBlock = continueInst->getTargetBlock(); - - UInt argCount = continueInst->getArgCount(); - static const UInt kFixedArgCount = 1; - emitPhiVarAssignments( - ctx, - argCount - kFixedArgCount, - continueInst->getArgs() + kFixedArgCount, - targetBlock); - - IRBlock* loopHead = nullptr; - ctx->shared->irMapContinueTargetToLoopHead.TryGetValue(targetBlock, loopHead); - SLANG_ASSERT(loopHead); - emitIRStmtsForBlocks( - ctx, - targetBlock, - loopHead); - emit("continue;\n"); - } - return; - - case kIROp_loopTest: - { - // Loop condition being tested - auto t = (IRLoopTest*)terminator; - - auto afterBlock = t->getTrueBlock(); - auto exitBlock = t->getFalseBlock(); - - emit("if("); - emitIROperand(ctx, t->getCondition()); - emit(")\n{} else {\n"); - emitIRStmtsForBlocks( - ctx, - exitBlock, - nullptr); - emit("}\n"); - - // Continue with the block after the test - block = afterBlock; - } - break; -#endif - - case kIROp_unconditionalBranch: - { - // Unconditional branch as part of normal - // control flow. This is either a forward - // edge to the "next" block in an ordinary - // block, or a backward edge to the top - // of a loop. - auto t = (IRUnconditionalBranch*)terminator; - auto targetBlock = t->getTargetBlock(); - - UInt argCount = t->getOperandCount(); - static const UInt kFixedArgCount = 1; - emitPhiVarAssignments( - ctx, - argCount - kFixedArgCount, - t->getOperands() + kFixedArgCount, - targetBlock); - - block = t->getTargetBlock(); + // Continue with the region after the loop + region = loopRegion->nextRegion; + continue; } - break; - - case kIROp_conditionalBranch: - // Note: We currently do not generate any plain - // `conditionalBranch` instructions when lowering - // to IR, because these would not have the annotations - // needed to be able to emit high-level control - // flow from them. - SLANG_UNEXPECTED("terminator inst"); - return; - - case kIROp_switch: + case Region::Flavor::Switch: { - // A `switch` instruction will always translate - // to a `switch` statement, but we need to - // take some care to emit the `case`s in ways - // that avoid code duplication. - - // TODO: Eventually, the "right" way to handle `switch` - // statements while being more robust about Duff's Device, etc. - // would be to register each of the case labels in a lookup - // table, and then walk the blocks in the region between - // the `switch` and the `break` and then whenever we see a block - // that matches one of the registered labels, emit the appropriate - // `case ...:` or `default:` label. - - auto t = (IRSwitch*) terminator; - - // Extract the fixed arguments. - auto conditionVal = t->getCondition(); - auto breakLabel = t->getBreakLabel(); - auto defaultLabel = t->getDefaultLabel(); - - // Register the block to be used for our `break` target - LabelStack subLabels; - subLabels.parent = labels; - subLabels.op = kLabelOp_break; - subLabels.block = breakLabel; - - // We need to track whether we've dealt with - // the `default` case already. - bool defaultLabelHandled = false; - - // If the `default` case just branches to - // the join point, then we don't need to - // do anything with it. - if(defaultLabel == breakLabel) - defaultLabelHandled = true; + auto switchRegion = (SwitchRegion*) region; // Emit the start of our statement. emit("switch("); - emitIROperand(ctx, conditionVal, IREmitMode::Default); + emitIROperand(ctx, switchRegion->condition, IREmitMode::Default); emit(")\n{\n"); - // Now iterate over the `case`s of the branch - UInt caseIndex = 0; - UInt caseCount = t->getCaseCount(); - while(caseIndex < caseCount) + auto defaultCase = switchRegion->defaultCase; + for(auto currentCase : switchRegion->cases) { - // We are going to extract one case here, - // but we might need to fold additional - // cases into it, if they share the - // same label. - // - // Note: this makes assumptions that the - // IR code generator orders cases such - // that: (1) cases with the same label - // are consecutive, and (2) any case - // that "falls through" to another must - // come right before it in the list. - auto caseVal = t->getCaseValue(caseIndex); - auto caseLabel = t->getCaseLabel(caseIndex); - caseIndex++; - - // Emit the `case ...:` for this case, and any - // others that share the same label - for(;;) + for(auto caseVal : currentCase->values) { emit("case "); emitIROperand(ctx, caseVal, IREmitMode::Default); emit(":\n"); - - if(caseIndex >= caseCount) - break; - - auto nextCaseLabel = t->getCaseLabel(caseIndex); - if(nextCaseLabel != caseLabel) - break; - - caseVal = t->getCaseValue(caseIndex); - caseIndex++; } - - // The label for the current `case` might also - // be the label used by the `default` case, so - // check for that here. - if(caseLabel == defaultLabel) + if(currentCase.Ptr() == defaultCase) { emit("default:\n"); - defaultLabelHandled = true; - } - - // Now we need to emit the statements that make - // up this case. The 99% case will be that it - // will terminate with a `break` (or a `return`, - // `continue`, etc.) and so we can pass in - // `nullptr` for the ending block. - IRBlock* caseEndLabel = nullptr; - - // However, there is also the possibility that - // this case will fall through to the next, and - // so we need to prepare for that possibility here. - // - // If there is a next case, then we will set its - // label up as the "end" label when emitting - // the statements inside the block. - if(caseIndex < caseCount) - { - caseEndLabel = t->getCaseLabel(caseIndex); } - // Now emit the statements for this case. indent(); emit("{\n"); indent(); - emitIRStmtsForBlocks(ctx, caseLabel, caseEndLabel, &subLabels); - dedent(); - emit("}\n"); - dedent(); - } - - // If we've gone through all the cases and haven't - // managed to encounter the `default:` label, - // then assume it is a distinct case and handle it here. - if(!defaultLabelHandled) - { - emit("default:\n"); - indent(); - emit("{\n"); - indent(); - emitIRStmtsForBlocks(ctx, defaultLabel, breakLabel, &subLabels); - emit("break;\n"); + emitRegion(ctx, currentCase->body); dedent(); emit("}\n"); dedent(); } emit("}\n"); - block = breakLabel; + // Continue with the region after the `switch` + region = switchRegion->nextRegion; + continue; } break; } - - // After we've emitted the first block, we are safe from accidental - // cases where we'd emit an entire loop body as a single `continue`, - // so we can safely switch in whatever labels are intended to be used. - useLabels = labels; - - // If we reach this point, then we've emitted - // one block, and we have a new block where - // control flow continues. - // - // We need to handle a special case here, - // when control flow jumps back to the - // starting block of the range we were - // asked to work with: - if (block == begin) return; + break; } } + /// Emit high-level language statements from a structrured region tree. + void emitRegionTree( + EmitContext* ctx, + RegionTree* regionTree) + { + emitRegion(ctx, regionTree->rootRegion); + } + // Is an IR function a definition? (otherwise it is a declaration) bool isDefinition(IRFunc* func) { @@ -4527,6 +4281,39 @@ struct EmitVisitor } } + /// Emit high-level statements for the body of a function. + void emitIRFunctionBody( + EmitContext* ctx, + IRGlobalValueWithCode* code) + { + // Compute a structured region tree that can represent + // the control flow of our function. + // + RefPtr<RegionTree> regionTree = generateRegionTreeForFunc( + code, + ctx->getSink()); + + // Now that we've computed the region tree, we have + // an opportunity to perform some last-minute transformations + // on the code to make sure it follows our rules. + // + // TODO: it would be better to do these transformations earlier, + // so that we can, e.g., dump the final IR code *before* emission + // starts, but that gets a bit compilcated because we also want + // to have the region tree avalable without having to recompute it. + // + // For now we are just going to do things the expedient way, but + // eventually we should allow an IR module to have side-band + // storage for dervied structured like the region tree (and logic + // for invalidating them when a transformation would break them). + // + fixValueScoping(regionTree); + + // Now emit high-level code from that structured region tree. + // + emitRegionTree(ctx, regionTree); + } + void emitIRSimpleFunc( EmitContext* ctx, IRFunc* func) @@ -4591,8 +4378,7 @@ struct EmitVisitor emitPhiVarDecls(ctx, func); // Need to emit the operations in the blocks of the function - - emitIRStmtsForBlocks(ctx, func->getFirstBlock(), nullptr, nullptr); + emitIRFunctionBody(ctx, func); dedent(); emit("}\n\n"); @@ -5457,7 +5243,7 @@ struct EmitVisitor emitIRType(ctx, varType, initFuncName); Emit("()\n{\n"); indent(); - emitIRStmtsForBlocks(ctx, varDecl->getFirstBlock(), nullptr, nullptr); + emitIRFunctionBody(ctx, varDecl); dedent(); Emit("}\n"); } diff --git a/source/slang/ir-legalize-types.cpp b/source/slang/ir-legalize-types.cpp index 969e3eb96..86907dfde 100644 --- a/source/slang/ir-legalize-types.cpp +++ b/source/slang/ir-legalize-types.cpp @@ -1462,7 +1462,7 @@ static void legalizeTypes( // Clean up after any instructions we replaced along the way. for (auto& lv : context->replacedInstructions) { - lv->deallocate(); + lv->removeAndDeallocate(); } } diff --git a/source/slang/ir-restructure-scoping.cpp b/source/slang/ir-restructure-scoping.cpp new file mode 100644 index 000000000..61b56e190 --- /dev/null +++ b/source/slang/ir-restructure-scoping.cpp @@ -0,0 +1,434 @@ +// ir-restructure-scoping.cpp +#include "ir-restructure-scoping.h" + +#include "ir.h" +#include "ir-insts.h" +#include "ir-restructure.h" + +namespace Slang +{ + +/// Try to find the first structured region that represents `block` +/// +/// In general the same block may appear as multiple regions, +/// so this will return the first region in the linked list. +static SimpleRegion* getFirstRegionForBlock( + RegionTree* regionTree, + IRBlock* block) +{ + SimpleRegion* region = nullptr; + if( regionTree->mapBlockToRegion.TryGetValue(block, region) ) + { + return region; + } + return nullptr; +} + +/// Try to find the first structured region that contains `inst`. +static SimpleRegion* getFirstRegionForInst( + RegionTree* regionTree, + IRInst* inst) +{ + auto ii = inst; + while(ii) + { + if(auto block = as<IRBlock>(ii)) + return getFirstRegionForBlock(regionTree, block); + + ii = ii->getParent(); + } + + return nullptr; +} + +/// Compute the depth of a node in the region tree. +/// +/// This is the number of nodes (including `region`) +/// on a path from `region` to the root. +/// +static Int computeDepth(Region* region) +{ + Int depth = 0; + for( Region* rr = region; rr; rr = rr->getParent() ) + { + depth++; + } + return depth; +} + +/// Get the `n`th ancestor of `region`. +/// +/// When `n` is zero, this returns `region`. +/// When `n` is one, this returns the parent of `region`, and so forth. +/// +static Region* getAncestor(Region* region, Int n) +{ + Region* rr = region; + for( Int ii = 0; ii < n; ++ii ) + { + SLANG_ASSERT(rr); + rr = rr->getParent(); + } + return rr; +} + +/// Find a region that is an ancestor of both `left` and `right`. +static Region* findCommonAncestorRegion( + Region* left, + Region* right) +{ + // Rather than blinding search through each ancestor of `left` + // and see if it is also an ancestor of `right` and vice-versa, + // let's try to be smart about this. + // + // We will start by computing the depth of `left` and `right`: + // + Int leftDepth = computeDepth(left); + Int rightDepth = computeDepth(right); + + // Whatever the common ancestor is, it can't be any deeper + // than the minimum of these two depths. + // + Int minDepth = Math::Min(leftDepth, rightDepth); + + // Let's fetch the ancestor of each of `left` and `right` + // corresponding to that depth: + // + Region* leftAncestor = getAncestor(left, leftDepth - minDepth); + Region* rightAncestor = getAncestor(right, rightDepth - minDepth); + + // Now we know that `leftAncestor` and `rightAncestor` + // must have the same depth. Let's go ahead and assert + // it just to be safe: + // + SLANG_ASSERT(computeDepth(leftAncestor) == minDepth); + SLANG_ASSERT(computeDepth(rightAncestor) == minDepth); + + // If `leftAncestor` and `rightAncestor` are the same node, + // then we've found a common ancestor, otherwise we should + // look at their parents. Because the depth must match + // on both sides, we will never risk missing an ancestor. + // + while( leftAncestor != rightAncestor ) + { + leftAncestor = leftAncestor->getParent(); + rightAncestor = rightAncestor->getParent(); + } + + // Okay, we've found a common ancestor. + // + Region* commonAncestor = leftAncestor; + return commonAncestor; +} + +/// Find a simple region that is an ancestor of both `left` and `right`. +static SimpleRegion* findSimpleCommonAncestorRegion( + Region* left, + Region* right) +{ + // Start by finding a common ancestor without worrying about it being simple. + Region* ancestor = findCommonAncestorRegion(left, right); + + // Now search for a simple region up the tree. + while( ancestor ) + { + if(ancestor->getFlavor() == Region::Flavor::Simple) + return (SimpleRegion*) ancestor; + + ancestor = ancestor->getParent(); + } + + // This shouldn't ever occur. The root of the region tree should + // be a simple regions that represents the entry block of the + // function. + // + SLANG_UNEXPECTED("no common ancestor found in region tree"); + UNREACHABLE_RETURN(nullptr); +} + +IRInst* getDefaultInitVal( + IRBuilder* builder, + IRType* type) +{ + switch( type->op ) + { + default: + return nullptr; + + case kIROp_BoolType: + return builder->getBoolValue(false); + + case kIROp_IntType: + case kIROp_UIntType: + case kIROp_UInt64Type: + return builder->getIntValue(type, 0); + + case kIROp_HalfType: + case kIROp_FloatType: + case kIROp_DoubleType: + return builder->getFloatValue(type, 0.0); + + // TODO: handle vector/matrix types here, by + // creating an appropriate scalar value and + // then "splatting" it. + } +} + +/// Initialize a variable to a sane default value, if possible. +void defaultInitializeVar( + IRBuilder* builder, + IRVar* var, + IRType* type) +{ + IRInst* initVal = nullptr; + switch( type->op ) + { + case kIROp_VoidType: + default: + // By default, see if we can synthesize an IR value + // to be used as the default, and allow the logic + // below to store it into the variable. + initVal = getDefaultInitVal(builder, type); + break; + + // TODO: Handle aggregate types (structures, arrays) + // explicitly here, since they need to be careful about + // the cases where an element/field type might not + // be something we can default-initialize. + } + + if( initVal ) + { + builder->emitStore(var, initVal); + } +} + +/// Detect and fix any structured scoping issues for a given `def` instruction. +/// +/// The `defRegion` should be the region that contains `def`, and `regionTree` +/// should be the region tree for the function that contains `def`. +/// +static void fixValueScopingForInst( + IRInst* def, + SimpleRegion* defRegion, + RegionTree* regionTree) +{ + // This algorithm should not consider "phi nodes" for now, + // because the emit logic will already create variables for them. + // We could consider folding the logic to move out of SSA form + // into this function, but that would add a lot of complexity for now. + if(def->op == kIROp_Param) + return; + + // We would have a scoping violation if there exists some + // use `u` of `def` such that the region containing `u` + // (call it `useRegion`) is not a descendent of `defRegion` + // in the region tree. + // + // If there are no scoping violations, we don't want to do + // anything. If there *are* any scoping violations, then + // we ill need to introduce a temporary `tmp`, store into + // it right after `def`, and then load from it at any "bad" + // use sites. + // + // Of course, for the whole thing to work, we also need + // to put `tmp` into a block somwhere, and it needs to + // be a block that is visible to all of the uses, or we + // are just back int the same mess again. + // + // The right block to use for inserting `tmp` is the least + // common ancestor of `def` and all the "bad" uses, so + // we will get a bit "clever" and fold in the search for + // bad uses with the computation of the region we should + // insert `tmp` into (to avoid looping over the uses + // twice). + // + SimpleRegion* insertRegion = defRegion; + IRVar* tmp = nullptr; + + // If we end up needing to insert code we'll need an IR builder, + // so we will go ahead and create one now. + // + // TODO: the logic to compute `module` here could be hoisted + // out earlier, rather than being done per-instruction. + // + IRModule* module = regionTree->irCode->getModule(); + + SharedIRBuilder sharedBuilder; + sharedBuilder.session = module->session; + sharedBuilder.module = module; + + IRBuilder builder; + builder.sharedBuilder = &sharedBuilder; + + // Because we will be changing some of the uses of `def` + // to use other values while we iterate the list, we + // need to be a bit careful and extract the next use + // in the linked list *before* we operator on `u`. + // + IRUse* nextUse = nullptr; + for( auto u = def->firstUse; u; u = nextUse ) + { + nextUse = u->nextUse; + + // Looking at the use site `u`, we'd like to check if + // it violates our scoping rules. + // + // As a simple early-exit case, if the user is in + // the same block as the definition, there are no problems. + // + IRInst* user = u->getUser(); + if(user->getParent() == defRegion->block) + continue; + + // Otherwise, let's find the structures control-flow + // region that holds the user. We expect to always + // find one, because the use site must be in the same + // function. + // + // TODO: Double check that logic if we ever introduce + // things like nested function. + // + SimpleRegion* useRegion = getFirstRegionForInst(regionTree, user); + + // If there is no region associated with the use, then + // the use must be in unreachable code (part of the CFG, + // but not part of the region tree). We will skip + // such uses for now, since they won't even appear in + // the output. + // + if(!useRegion) + continue; + + // Now we want to check if `useRegion` is a child/descendent + // of a region that has the same block as `defRegion`. + // If it is, then there is no scoping problem with this use. + // + if(useRegion->isDescendentOf(defRegion->block)) + continue; + + // If we've gotten this far, we know that `u` is a "bad" + // use of `def`, and needs fixing. + // + // We will create the `tmp` variable on demand, so + // that we create it when the first "bad" use is encountered, + // and then re-use it for subsequent bad uses. + // + if( !tmp ) + { + // We will create a temporary to represent `def`, + // and insert a `store` into it right after `def`. + // + // Note: we are inserting the new variable right + // after `def` for now, just because we don't + // yet know the final region that it should be + // placed into. We will move it to the correct + // location when we are done. + // + builder.setInsertBefore(def->getNextInst()); + tmp = builder.emitVar(def->getDataType()); + builder.emitStore(tmp, def); + } + + // In order to know where `tmp` should be defined + // at the end of the algorithm, we need to compute + // a valid `insertRegion` that is an ancestor of + // all of the use sites (and it also a simple region + // so that we can insert into its IR block). + // + // We need to deal with one complexity in our restructuring + // process, which is that a block may be duplicated into + // one or more regions, so we loop over all the regions + // for the same block as `useRegion`. + // + for(auto rr = useRegion; rr; rr = rr->nextSimpleRegionForSameBlock) + { + insertRegion = findSimpleCommonAncestorRegion( + insertRegion, + rr); + } + + // To fix up the use `u`, we will need to change + // it from using `def` to using a load from `tmp` + // + builder.setInsertBefore(user); + IRInst* tmpVal = builder.emitLoad(tmp); + + // We are clobbering the value used by the `IRUse` `u`, + // while will cut it out of the list of uses for `def`. + // We need to be careful when doing this to not disrupt + // our iteration of the uses of `def`, so we carefully + // used the `nextUse` temporary at the start of the loop. + // + u->set(tmpVal); + } + + // At the end of the loop, the `tmp` variable will have + // been created if and only if we fixed up anything. + // + if( tmp ) + { + // If we created a temporary, then now we need to move + // its definition to the right place, which is the + // `insertRegion` that we computed during the loop. + // + // We'd like to insert our temporary near the top + // of the region, since that is the conventional + // place for local variables to go. + // + tmp->insertBefore( + insertRegion->block->getFirstOrdinaryInst()); + + // The whole point of the transformation we are doing + // here is that `def` is not on the "obvious" control + // flow path to one or more uses (which are now using + // `tmp`), but that means that it might not be "obvious" + // to a downstream compiler that `tmp` always gets + // initialized (by the code we inserted after `def`) + // before each of these use sites. + // + // We *know* that things are valid as long as our + // dominator tree was valid - there is no way to + // get to the block that loads from `tmp` without passing + // through the block that computes `def` (and then + // stores it into `tmp`) first. + // + // To avoid warnings/errros, we will go ahead and try + // to emit logic to "default initialize" the `tmp` + // variable if possible. + // + builder.setInsertBefore(tmp->getNextInst()); + defaultInitializeVar(&builder, tmp, def->getDataType()); + } +} + +void fixValueScoping(RegionTree* regionTree) +{ + // We are going to have to walk through every instruction + // in the code of the function to detect an bad cases. + // + auto code = regionTree->irCode; + for(auto block : code->getBlocks()) + { + // All of the instruction in `block` will have the same + // parent region, so we will look it up now rather than + // have to re-do this work on a per-instruction basis. + // + auto parentRegion = getFirstRegionForBlock(regionTree, block); + + // If a block has no region then it must be unreachable, + // so we will skip it entirely for this pass. + // + // TODO: we should be eliminating unrechable blocks anyway. + // + if(!parentRegion) + continue; + + for(auto inst : block->getChildren()) + { + fixValueScopingForInst(inst, parentRegion, regionTree); + } + } +} + +} diff --git a/source/slang/ir-restructure-scoping.h b/source/slang/ir-restructure-scoping.h new file mode 100644 index 000000000..7840dda80 --- /dev/null +++ b/source/slang/ir-restructure-scoping.h @@ -0,0 +1,24 @@ +// ir-restructure-scoping.h +#pragma once + +namespace Slang +{ + +class RegionTree; + +/// Fix cases where a value might be used in a non-nested region. +/// +/// There can be cases where an IR value V in block A is used in +/// some block B, where A dominates B, *but* when we constructed +/// the region tree, the block B is not in a child/descendent +/// region of A's region, so that it won't be visible through the +/// scoping rules of a target language. +/// +/// This function detects such cases, and fixes them up by inserting +/// new temporaries into the IR code so that values that need +/// to survive across blocks are communicated through variables +/// declared at a sufficiently broad scope. +/// +void fixValueScoping(RegionTree* regionTree); + +} diff --git a/source/slang/ir-restructure.cpp b/source/slang/ir-restructure.cpp new file mode 100644 index 000000000..98311b11b --- /dev/null +++ b/source/slang/ir-restructure.cpp @@ -0,0 +1,662 @@ +// ir-restructure.cpp +#include "ir-restructure.h" + +#include "ir.h" +#include "ir-insts.h" + +namespace Slang +{ + bool Region::isDescendentOf(Region* other) + { + Region* rr = this; + while( rr ) + { + if(rr == other) + return true; + + rr = rr->getParent(); + } + return false; + } + + bool Region::isDescendentOf(IRBlock* block) + { + Region* rr = this; + while( rr ) + { + if( rr->getFlavor() == Region::Flavor::Simple ) + { + SimpleRegion* simpleRegion = (SimpleRegion*) rr; + if(simpleRegion->block == block) + return true; + } + + rr = rr->getParent(); + } + return false; + } + + /// An "active" label during control flow (re)structuring. + struct LabelStack + { + /// Possible operations associated with labels. + enum class Op + { + Break, + Continue, + + CountOf, + }; + + /// What kind of operation does a branch to this label represent? + Op op; + + /// The next label down on the stack + LabelStack* parent; + + /// The block the represents this label in the IR control flow graph. + IRBlock* block; + + /// The region that represents this label in the structured program + Region* region; + }; + + /// State used when restructuring control flow. + struct ControlFlowRestructuringContext + { + /// Sink to use when diagnosing errors in control-flow restructuring. + /// + /// The restructuring pass should be able to handle anything the front-end + /// throws at it, so these errors will all be unexpected. Still, we need + /// a way to report them cleanly without crashing the process. + /// + DiagnosticSink* sink = nullptr; + DiagnosticSink* getSink() { return sink; } + + /// The region tree we are in the process of building. + RegionTree* regionTree = nullptr; + }; + + /// Convert a range of blocks in the IR CFG into a region. + /// + /// We want to generate a region that stands in for the + /// blocks that are logically in the internal [begin, end) + /// which we consider as representing a single-entry multiple-exit + /// sub-graph. Note that `end` is *not* part of the sub-graph, + /// but instead points to a block that is logically "after" + /// the sub-graph. `end` can be `null` to indicate that the + /// sub-graph extends as far as possible. + /// + /// Because there can be multiple exits, control flow may + /// exit the sub-graph without branching to `end`, any + /// such "non-local" branching should be to one of the + /// blocks stored in the current `LabelStack`. + /// + // TODO: Eventually we should replace all of this logic with + // a variation on the "Relooper" algorithm as it is used + // in Emscripten. + // + static RefPtr<Region> generateRegionsForIRBlocks( + ControlFlowRestructuringContext* ctx, + Region* inParentRegion, + IRBlock* begin, + IRBlock* end, + LabelStack* initialLabels, // Labels to use at the start + LabelStack* labels = nullptr) // Labels to switch to after emitting first basic block + { + if(!labels) + labels = initialLabels; + auto useLabels = initialLabels; + + // + // We will try to build up as long of a sequential/simple region + // as possible, to avoid deep recursion in this algorithm. + // + RefPtr<Region> resultRegion = nullptr; + RefPtr<Region>* resultLink = &resultRegion; + + // As we move along, the parent region to use for regions + // we create will shift, so we need a temporary to track + // the current parent region. + // + Region* parentRegion = inParentRegion; + + // + // We will start with the `begin` block, and try to proceed + // sequentially until we see the `end` block, or run into + // an edge that exits teh region. + // + IRBlock* block = begin; + while(block != end) + { + // If the block we are trying to emit has been registered as a + // destination label (e.g. for a loop or `switch`) then we + // need to exit the current region, which amounts to generating + // a `break` or `continue` operation. + // + // TODO: we eventually need to handle the possibility of + // multi-level break/continue targets, which could be challenging. + + // Because we will only support single-level break/continue, we + // want to resolve what is the most recent label that is "active" + // for the given operation (`break` or `continue`). + // + // We will do this with a naive loop, just to keep things simple. + // We start with no block "regsitered" as the target for each + // operation. + // + IRBlock* registeredBlock[(int)LabelStack::Op::CountOf] = {}; + for( auto ll = useLabels; ll; ll = ll->parent ) + { + // For each active label, see if it is the first one + // we encounter for the given op. + // + if(!registeredBlock[(int)ll->op]) + { + registeredBlock[(int)ll->op] = ll->block; + } + } + + // Next we will search through *all* of the registered labels, + // and see if one of them matches the current `block`. + // + for(auto ll = useLabels; ll; ll = ll->parent) + { + // Does this label match the block we are trying to translate? + if(ll->block != block) + continue; + + // Okay, the block we are trying to generate code for is a label + // that we should branch to (we shouldn't just emit the code here + // and now...) + // + // We should first confirm that the block is the inner-most label + // registered for the given control-flow op (`break` or `continue`) + // because if it *isn't* we currently can't generate code. + // + if(block != registeredBlock[(int)ll->op]) + { + ctx->getSink()->diagnose(block, Diagnostics::multiLevelBreakUnsupported); + } + + // Now we need to create a structured `break` or `continue` operation + // to match the operation associated with the target. + // + switch(ll->op) + { + case LabelStack::Op::Break: + { + auto outerRegion = (BreakableRegion*) ll->region; + RefPtr<BreakRegion> breakRegion = new BreakRegion(parentRegion, outerRegion); + + *resultLink = breakRegion; + resultLink = nullptr; + } + break; + + case LabelStack::Op::Continue: + { + auto outerRegion = (LoopRegion*) ll->region; + RefPtr<ContinueRegion> continueRegion = new ContinueRegion(parentRegion, outerRegion); + + *resultLink = continueRegion; + resultLink = nullptr; + } + break; + } + + // If the `block` matched an active label, then we should have + // created a branch, and there is nothing to be done here. + return resultRegion; + } + + // We now know that the given `block` is part of our control-flow region, + // so we need to output a simple region that executes the code in that block. + // + RefPtr<SimpleRegion> simpleRegion = new SimpleRegion(parentRegion, block); + + // We need to register the mapping from `block` to this region, but in + // general this isn't a one-to-one mapping, but rather one-to-many. + // This is because a "continue clause" in a `for` loop might get duplicated + // at each `continue` site in the output code. To deal with this + // we build a singly-linked list of regions for each block. + // + // TODO: confirm that continue clauses are the only case that leads + // to duplication. + // + // TODO: remove this workaround once we have a more powerful restructuring + // pass that avoids duplicating blocks (by introducing new temporaries...) + // + SimpleRegion* nextSimpleRegionForSameBlock = nullptr; + ctx->regionTree->mapBlockToRegion.TryGetValue(block, nextSimpleRegionForSameBlock); + ctx->regionTree->mapBlockToRegion[block] = simpleRegion; + + *resultLink = simpleRegion; + resultLink = &simpleRegion->nextRegion; + parentRegion = simpleRegion; + + // The simple region we created will represent all of the non-terminator + // instructions in the `block`, so now we need to figure out what to + // create to represent that terminator. + // + auto terminator = block->getTerminator(); + SLANG_ASSERT(terminator != nullptr); + switch (terminator->op) + { + default: + case kIROp_conditionalBranch: + // Note: we don't currently generate ordinary `conditionalBranch` instructions, + // and instead only generate `ifElse` instructions, which include additional + // information that can inform our control-flow restructuring pass. + // + SLANG_UNEXPECTED("unhandled terminator instruction opcode"); + // fall through to: + case kIROp_unreachable: + case kIROp_ReturnVal: + case kIROp_ReturnVoid: + case kIROp_discard: + // These cases are all simple terminators that can be handled as-is + // without needing to construct a separate `Region` to encapsulate them. + // + // We will cap off the current sequence of simple regions and return. + // + *resultLink = nullptr; + return resultRegion; + + case kIROp_ifElse: + { + // Here we have a two-way branch, so that we will construct a + // region representing an `if` statement. + // + auto ifInst = (IRIfElse*)terminator; + auto condition = ifInst->getCondition(); + auto trueBlock = ifInst->getTrueBlock(); + auto falseBlock = ifInst->getFalseBlock(); + auto afterBlock = ifInst->getAfterBlock(); + + + RefPtr<IfRegion> ifRegion = new IfRegion(parentRegion, condition); + + // The region for the "then" part of things will consist of + // the range of blocks `[trueBlock, afterBlock)`. + // + // This logic assumes that `afterBlock` is a valid structured + // "join point" such that any branch out of the sub-region + // either leads to `afterBlock` *or* one of the labels + // that is already present on our label stack. + // + ifRegion->thenRegion = generateRegionsForIRBlocks( + ctx, + ifRegion, + trueBlock, + afterBlock, + labels); + + // Generating a region for the `else` part is similar. + // Note that it is possible for this to be a `null` + // region, if `falseBlock == afterBlock`. + // + ifRegion->elseRegion = generateRegionsForIRBlocks( + ctx, + ifRegion, + falseBlock, + afterBlock, + labels); + + *resultLink = ifRegion; + resultLink = &ifRegion->nextRegion; + parentRegion = ifRegion; + + // Continue with the block after the `ifElse` instruction. + block = afterBlock; + } + break; + + case kIROp_loop: + { + // The terminator in this case is the header for a structured loop. + // + auto loopInst = (IRLoop*) terminator; + auto bodyBlock = loopInst->getTargetBlock(); + auto afterBlock = loopInst->getBreakBlock(); + + RefPtr<LoopRegion> loopRegion = new LoopRegion(parentRegion, loopInst); + + // We will need to set up entries on our label stack to + // represent the targets for `break` or `continue` + // operations inside the loop. + // + // First we set up the stack entry for the `break` label, + // which will refer to the block *after* the loop. + // + // The region we specify for the label will still be + // the loop region, though, because the loop is what + // we are breaking out of. + // + LabelStack loopBreakLabelStack; + loopBreakLabelStack.parent = labels; + loopBreakLabelStack.block = afterBlock; + loopBreakLabelStack.region = loopRegion; + loopBreakLabelStack.op = LabelStack::Op::Break; + + // + // The `continue` label warrants a bit more careful explanation, + // because it will *not* refer to the block that was regsitered + // as the continue target in the IR `loop` instruction. This + // is because we will always emit our loops as `for(;;) { ... }` + // with no continue clause at all, so that a `continue` in + // the output code will always refer to the top of the loop. + // + // This means that the `continue` label for the purposes of + // structured control flow will be the start of the loop body: + // + LabelStack loopContinueLabelStack; + loopContinueLabelStack.parent = &loopBreakLabelStack; + loopContinueLabelStack.block = bodyBlock; + loopContinueLabelStack.region = loopRegion; + loopContinueLabelStack.op = LabelStack::Op::Continue; + // + // Note: by ignoring the original continue block from the + // high-level loop, we create a situation where that code + // might get emitted more than once (once per implicit + // or explicit `continue` site in the original program). + // + // That is an acceptable trade-off for now, because continue + // blocks will usually be small (and fxc makes the same choice), + // but it could lead to Bad Things if somebody were to call + // a function in their continue clause, and that function does + // a compute shader barrier operation. + // + // A better long-term fix is to take a high-level loop like: + // + // for(A; B; C) { ... continue; ... break; ... } + // + // and translate it into something like the following (assuming + // we have labeled statements and multi-level `break`): + // + // A; + // Outer: for(;;) { + // Inner: for(;;) { + // if(B) {} else break Outer; + // ... + // break Inner; // `continue` becomes break of inner loop + // ... + // break Outer; // `break` becomes break of outer loop + // ... + // break; // inner loop unconditionally breaks at the end + // } + // C; // continue clause comes after inner loop + // } + // + // If you draw up a control flow graph for that code, you'll find + // it is equivalent to the orignal `for` loop, but now supports + // arbitrary code (not just a single expression) for the continue clause. + // Unlike the current code-duplication solution, `C` appears only once + // in the output, and seems to clearly be at a "joint point" for control + // flow so that it is clear that a barrier there is valid in GLSL. + // + // Anyway, back our regularly scheduled programming. + // + // With the label stack stuff set up, we want to take the region + // of the CFG defined by `[bodyBlock, afterBlock)` and turn it into + // the body region for our loop. + // + // The only thing we want to be a little bit careful about is + // that we don't want the logic at the top of this function + // that looks for a block it can translate into a `continue` + // to trigger on `bodyBlock`, since that means we'd just turn + // the whole body into a single `continue`. + // + // To avoid this problem, we pass in two different label stacks: + // one to use for the first block, and one to use for subsequent + // blocks. + // + loopRegion->body = generateRegionsForIRBlocks( + ctx, + loopRegion, + bodyBlock, + // TODO: should we pass `afterBlock` here instead of `null`? + nullptr, + // For the first block, we only want the `break` label active + &loopBreakLabelStack, + // After the first block, we can safely use the `continue` label too + &loopContinueLabelStack); + + *resultLink = loopRegion; + resultLink = &loopRegion->nextRegion; + parentRegion = loopRegion; + + // Continue with the block after the loop + block = afterBlock; + } + break; + + case kIROp_unconditionalBranch: + { + // Here we have an unconditional branch that was + // not covered by one of our labels for non-local + // branches (`break` or `continue`). + // + // We will thus assume that the target of the + // branch is part of the same region we are building, + // and continue with the target block; + // + auto branchInst = (IRUnconditionalBranch*) terminator; + block = branchInst->getTargetBlock(); + } + break; + + case kIROp_switch: + { + // A `switch` instruction will always translate + // to a `SwitchRegion` and then to a `switch` statement. + // + // We will need to take care to emit `case`s in ways + // that avoid code duplication. + // + // The logic here isn't going to be robust in edge cases + // (please don't write Duff's Device in Slang just yet). + // Doing significantly better than what is here would + // require something like the Relooper algorithm, though. + // + auto switchInst = (IRSwitch*) terminator; + auto condition = switchInst->getCondition(); + auto breakLabel = switchInst->getBreakLabel(); + auto defaultLabel = switchInst->getDefaultLabel(); + + RefPtr<SwitchRegion> switchRegion = new SwitchRegion(parentRegion, condition); + + // A direct branch to the block after the `switch` can + // be emitted as a `break` statement, so we will register + // the appropriate label on a label stack: + // + LabelStack switchBreakLabelStack; + switchBreakLabelStack.parent = labels; + switchBreakLabelStack.op = LabelStack::Op::Break; + switchBreakLabelStack.block = breakLabel; + switchBreakLabelStack.region = switchRegion; + + // We need to track whether we've dealt with + // the `default` case already. + // + bool defaultLabelHandled = false; + + // If the `default` case just branches to + // the join point, then we don't need to + // do anything with it. + // + if(defaultLabel == breakLabel) + defaultLabelHandled = true; + + // We will now iterate over the different `case`s, and + // try to group them together to minimize the number of + // sub-regions we have to create. + // + UInt caseIndex = 0; + UInt caseCount = switchInst->getCaseCount(); + while(caseIndex < caseCount) + { + // We are going to extract one case here, + // but we might need to fold additional + // cases into it, if they share the + // same label. + // + // Note: this makes assumptions that the + // IR code generator orders cases such + // that: (1) cases with the same label + // are consecutive, and (2) any case + // that "falls through" to another must + // come right before it in the list. + + auto caseVal = switchInst->getCaseValue(caseIndex); + auto caseLabel = switchInst->getCaseLabel(caseIndex); + caseIndex++; + + RefPtr<SwitchRegion::Case> currentCase = new SwitchRegion::Case(); + switchRegion->cases.Add(currentCase); + + // Add the case value for this case, and any + // others that share the same label + // + for(;;) + { + currentCase->values.Add(caseVal); + + // Are there any more `case`s left? + // + if(caseIndex >= caseCount) + break; + + // Does the next `case` share the same target label? + auto nextCaseLabel = switchInst->getCaseLabel(caseIndex); + if(nextCaseLabel != caseLabel) + break; + + // If those checks passed, then we will fold + // the next `case` into the same region, and + // keep looking. + caseVal = switchInst->getCaseValue(caseIndex); + caseIndex++; + } + + // The label for the current `case` might also + // be the label used by the `default` case, so + // check for that here. + // + if(caseLabel == defaultLabel) + { + switchRegion->defaultCase = currentCase; + defaultLabelHandled = true; + } + + // Now we need to generate a region for the instructions + // that make up this case. The 99% case will be that it + // will terminate with a `break` (or a `return`, + // `continue`, etc.) and so we can pass in `nullptr` + // for the ending block. + // + IRBlock* caseEndLabel = nullptr; + + // However, there is also the possibility that + // this `case` will fall through to the next, and + // so we need to prepare for that possibility here. + // + // If there *is* a next `case`, then we will set its + // label up as the "end" label when emitting + // the statements inside the block. + if(caseIndex < caseCount) + { + caseEndLabel = switchInst->getCaseLabel(caseIndex); + } + + // Now we can actually generate the region. + // + currentCase->body = generateRegionsForIRBlocks( + ctx, + switchRegion, + caseLabel, + caseEndLabel, + &switchBreakLabelStack); + } + + // If we've gone through all the cases and haven't + // managed to encounter the `default:` label, + // then assume it is a distinct case and handle it here. + if(!defaultLabelHandled) + { + RefPtr<SwitchRegion::Case> defaultCase = new SwitchRegion::Case(); + switchRegion->cases.Add(defaultCase); + + // Note: we use `null` instead of `breakLabel` as the end block + // here, to ensure that the `default` region will end with an + // explicit `break` rather than just falling off the end. + + defaultCase->body = generateRegionsForIRBlocks( + ctx, + switchRegion, + defaultLabel, + nullptr, + &switchBreakLabelStack); + + switchRegion->defaultCase = defaultCase; + } + + *resultLink = switchRegion; + resultLink = &switchRegion->nextRegion; + parentRegion = switchRegion; + + // Continue with the block after the `switch` + block = breakLabel; + } + break; + } + + // After we've emitted the first block, we are safe from accidental + // cases where we'd emit an entire loop body as a single `continue`, + // so we can safely switch in whatever labels are intended to be used. + useLabels = labels; + + // If we reach this point, then we've emitted + // one block, and we have a new block where + // control flow continues. + // + // We need to handle a special case here, + // when control flow jumps back to the + // starting block of the range we were + // asked to work with: + if (block == begin) + { + break; + } + } + + // We seem to have reached the rend of the region + // without anything special happening. This means + // we should cap off the current sequence of regions + // and return what we have. + // + *resultLink = nullptr; + return resultRegion; + } + + RefPtr<RegionTree> generateRegionTreeForFunc( + IRGlobalValueWithCode* code, + DiagnosticSink* sink) + { + RefPtr<RegionTree> regionTree = new RegionTree(); + regionTree->irCode = code; + + ControlFlowRestructuringContext restructuringContext; + restructuringContext.sink = sink; + restructuringContext.regionTree = regionTree; + + regionTree->rootRegion = generateRegionsForIRBlocks( + &restructuringContext, + nullptr, + code->getFirstBlock(), + nullptr, + nullptr); + + return regionTree; + } +} diff --git a/source/slang/ir-restructure.h b/source/slang/ir-restructure.h new file mode 100644 index 000000000..d27f7dbc8 --- /dev/null +++ b/source/slang/ir-restructure.h @@ -0,0 +1,261 @@ +// ir-restructure.h +#pragma once + +#include "../core/basic.h" + +namespace Slang +{ + class DiagnosticSink; + struct IRBlock; + struct IRGlobalValueWithCode; + struct IRInst; + struct IRLoop; + + /// A structured control-flow region. + /// + /// A `Region` is used to layer structured control flow information + /// over an existing IR control flow graph (CFG). Each `Region` + /// represents a sub-graph of the CFG such that control always + /// enters at the start of the region. + /// + class Region : public RefObject + { + public: + enum class Flavor + { + Simple, + If, + Break, + Continue, + Loop, + Switch, + }; + + Flavor getFlavor() { return flavor; } + + Region* getParent() { return parent; } + + /// Is this region a descendent of `other`? + /// + /// For the purpose of this query, a region + /// is a descendent of itself. + bool isDescendentOf(Region* other); + + /// Is this region a descendent of `block`? + /// + /// This tests is the region is a descendent + /// of any simple region for `block`. + bool isDescendentOf(IRBlock* block); + + protected: + Region(Flavor flavor, Region* parent) + : flavor(flavor) + , parent(parent) + {} + + /// What kind of region is this? + Flavor flavor; + + /// The parent region of this region. + Region* parent; + }; + + /// Base type for regions that have a "next" region. + /// + /// While we think of it as a region to execute + /// after this region, the `nextRegion` is actually + /// a *child* region, in that it can see local + /// values that were defined in this parent region + /// (and any other ancestor regions). + class SeqRegion : public Region + { + protected: + SeqRegion(Flavor flavor, Region* parent) + : Region(flavor, parent) + {} + + public: + /// The (child) region to execute after this one. + RefPtr<Region> nextRegion; + }; + + /// A simple region that encapsulates a basic block. + /// + class SimpleRegion : public SeqRegion + { + public: + SimpleRegion(Region* parent, IRBlock* block) + : SeqRegion(Region::Flavor::Simple, parent) + , block(block) + {} + + /// The basic block for this region. + IRBlock* block = nullptr; + + /// The next simple region for the same block + /// + /// A single IR basic block may turn into multiple regions, + /// if the restructuring pass has to duplicate it (this + /// currently happens for the continue clause in a `for` + /// loop if it has multiple `continue` sites. + /// + SimpleRegion* nextSimpleRegionForSameBlock = nullptr; + }; + + /// A conditional region, corresponding to an `if` + /// + class IfRegion : public SeqRegion + { + public: + IfRegion(Region* parent, IRInst* condition) + : SeqRegion(Region::Flavor::If, parent) + , condition(condition) + {} + + /// The IR value that controls the conditional branch + IRInst* condition; + + /// The region to execute if the `condition` is `true` + RefPtr<Region> thenRegion; + + /// The region to execute if the `condition` is `false` + RefPtr<Region> elseRegion; + }; + + /// Base type for regions that execution can `break` out of + class BreakableRegion : public SeqRegion + { + protected: + BreakableRegion(Flavor flavor, Region* parent) + : SeqRegion(flavor, parent) + {} + }; + + /// A region that expresses a `break` out of nested control flow. + /// + class BreakRegion : public Region + { + public: + BreakRegion(Region* parent, BreakableRegion* outerRegion) + : Region(Region::Flavor::Break, parent) + , outerRegion(outerRegion) + {} + + BreakableRegion* outerRegion; + }; + + /// A structured loop + class LoopRegion : public BreakableRegion + { + public: + LoopRegion(Region* parent, IRLoop* loopInst) + : BreakableRegion(Region::Flavor::Loop, parent) + , loopInst(loopInst) + {} + + /// The IR instruction that represents the branch into the loop. + /// We keep this instruction around because it may have decorations + /// that need to influence how we emit this loop. + /// + IRLoop* loopInst; + + /// The code inside the loop. + /// + /// The body region may include `break` or `continue` operations for this loop. + RefPtr<Region> body; + }; + + /// A region that expresses a `continue` for a structured loop. + /// + class ContinueRegion : public Region + { + public: + ContinueRegion(Region* parent, LoopRegion* outerRegion) + : Region(Region::Flavor::Continue, parent) + , outerRegion(outerRegion) + {} + + LoopRegion* outerRegion; + }; + + /// A structured `switch` statement. + class SwitchRegion : public BreakableRegion + { + public: + SwitchRegion(Region* parent, IRInst* condition) + : BreakableRegion(Region::Flavor::Switch, parent) + , condition(condition) + {} + + /// The IR value that controls the conditional branch + IRInst* condition; + + /// A collection of `case`s that share the same code. + class Case : public RefObject + { + public: + /// The various values that should branch to this case. + /// + /// It is possible for this list to be empty if this + /// is the `default` case and has no explicit values + /// that map to it. + /// + List<IRInst*> values; + + /// The region to execute if this case is selected. + RefPtr<Region> body; + }; + + /// All of the cases for the `switch`. + /// + /// This includes any `default` cases. + /// + /// As an invariant, a case that "falls through" to another + /// should immediately precede its target in this list. + /// + List<RefPtr<Case>> cases; + + /// The default case, if any. + /// + /// It is valid for this to be `null` if there is no `default` case, + /// in which case the default behavior should be to branch to the region + /// after the `switch`. + /// + /// The default case must also be present in `cases`. + Case* defaultCase; + }; + + /// Container for all of the regions in a function. + /// + /// A `RegionTree` owns the `Region` objects associated with a function, + /// along with a mapping from basic blocks in the IR function to regions + /// in the tree. + /// + class RegionTree : public RefObject + { + public: + /// Type for the mapping from IR blocks to regions. + typedef Dictionary<IRBlock*, SimpleRegion*> MapBlockToRegion; + + /// A dictionary to map from IR blocks to regions. + MapBlockToRegion mapBlockToRegion; + + /// The root region of the region tree. + RefPtr<Region> rootRegion; + + /// The IR function that was used to compute the region tree. + IRGlobalValueWithCode* irCode = nullptr; + }; + + /// Construct structrured regions to represent the control flow in an IR function. + /// + /// The resulting `RegionTree` will encode a structured (statement-like) + /// form for the control flow graph (CFG) of `code`. + /// In cases where our current restructuring approach is now powerful + /// enough to handle something in the input CFG, diagnostic messages + /// will be output to the given `sink`. + /// + RefPtr<RegionTree> generateRegionTreeForFunc( + IRGlobalValueWithCode* code, + DiagnosticSink* sink); +} diff --git a/source/slang/ir.cpp b/source/slang/ir.cpp index 408f4257d..92801ec9a 100644 --- a/source/slang/ir.cpp +++ b/source/slang/ir.cpp @@ -1564,6 +1564,7 @@ namespace Slang nullptr, nullptr); module->moduleInst = moduleInst; + moduleInst->module = module; return module; } @@ -2891,12 +2892,6 @@ namespace Slang ff->debugValidate(); } - void IRInst::deallocate() - { - // Run destructor to be sure... - this->~IRInst(); - } - void IRInst::dispose() { IRObject::dispose(); @@ -3055,6 +3050,7 @@ namespace Slang void IRInst::removeArguments() { + typeUse.clear(); for( UInt aa = 0; aa < operandCount; ++aa ) { IRUse& use = getOperands()[aa]; @@ -3068,7 +3064,9 @@ namespace Slang { removeFromParent(); removeArguments(); - deallocate(); + + // Run destructor to be sure... + this->~IRInst(); } bool IRInst::mightHaveSideEffects() @@ -3144,6 +3142,20 @@ namespace Slang } } + IRModule* IRInst::getModule() + { + IRInst* ii = this; + while(ii) + { + if(auto moduleInst = as<IRModuleInst>(ii)) + return moduleInst->module; + + ii = ii->getParent(); + } + return nullptr; + } + + // // Legalization of entry points for GLSL: // @@ -4563,8 +4575,7 @@ namespace Slang for( auto pp = firstBlock->getFirstParam(); pp; ) { auto next = pp->getNextParam(); - pp->removeFromParent(); - pp->deallocate(); + pp->removeAndDeallocate(); pp = next; } } diff --git a/source/slang/ir.h b/source/slang/ir.h index af08b9491..91ca377f2 100644 --- a/source/slang/ir.h +++ b/source/slang/ir.h @@ -247,10 +247,6 @@ struct IRInst : public IRObject // that this value will now have no uses. 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; @@ -297,6 +293,12 @@ struct IRInst : public IRObject // RTTI support static bool isaImpl(IROp) { return true; } + + /// Find the module that this instruction is nested under. + /// + /// If this instruction is transitively nested inside some IR module, + /// this function will return it, and will otherwise return `null`. + IRModule* getModule(); }; // `dynamic_cast` equivalent diff --git a/source/slang/slang.vcxproj b/source/slang/slang.vcxproj index f32355e83..284907018 100644 --- a/source/slang/slang.vcxproj +++ b/source/slang/slang.vcxproj @@ -185,6 +185,8 @@ <ClInclude Include="ir-dominators.h" /> <ClInclude Include="ir-inst-defs.h" /> <ClInclude Include="ir-insts.h" /> + <ClInclude Include="ir-restructure-scoping.h" /> + <ClInclude Include="ir-restructure.h" /> <ClInclude Include="ir-ssa.h" /> <ClInclude Include="ir-validate.h" /> <ClInclude Include="ir.h" /> @@ -229,6 +231,8 @@ <ClCompile Include="ir-constexpr.cpp" /> <ClCompile Include="ir-dominators.cpp" /> <ClCompile Include="ir-legalize-types.cpp" /> + <ClCompile Include="ir-restructure-scoping.cpp" /> + <ClCompile Include="ir-restructure.cpp" /> <ClCompile Include="ir-ssa.cpp" /> <ClCompile Include="ir-validate.cpp" /> <ClCompile Include="ir.cpp" /> diff --git a/source/slang/slang.vcxproj.filters b/source/slang/slang.vcxproj.filters index 991fe9c44..cb0235e61 100644 --- a/source/slang/slang.vcxproj.filters +++ b/source/slang/slang.vcxproj.filters @@ -1,4 +1,4 @@ -<?xml version="1.0" encoding="utf-8"?> +<?xml version="1.0" encoding="utf-8"?> <Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> <ItemGroup> <Filter Include="Header Files"> @@ -153,6 +153,10 @@ <ClInclude Include="vm.h"> <Filter>Header Files</Filter> </ClInclude> + <ClInclude Include="ir-restructure.h"> + <Filter>Header Files</Filter> + </ClInclude> + <ClInclude Include="ir-restructure-scoping.h" /> </ItemGroup> <ItemGroup> <ClCompile Include="bytecode.cpp"> @@ -254,6 +258,10 @@ <ClCompile Include="vm.cpp"> <Filter>Source Files</Filter> </ClCompile> + <ClCompile Include="ir-restructure.cpp"> + <Filter>Source Files</Filter> + </ClCompile> + <ClCompile Include="ir-restructure-scoping.cpp" /> </ItemGroup> <ItemGroup> <None Include="slang.natvis"> diff --git a/tests/bugs/gh-569.slang b/tests/bugs/gh-569.slang new file mode 100644 index 000000000..fa7525d45 --- /dev/null +++ b/tests/bugs/gh-569.slang @@ -0,0 +1,36 @@ +// gh-569.slang +//TEST(compute):COMPARE_COMPUTE: + +// Test that correct scoping is used in generated HLSL/GLSL, +// even when dominator tree and structured control flow disagree. + +uint test(uint inVal) +{ + uint tmp = inVal; + for(;;) + { + if(tmp < 4) + { + tmp++; + } + else + { + break; + } + } + return tmp + inVal; +} + +//TEST_INPUT:ubuffer(data=[0 0 0 0], stride=4):dxbinding(0),glbinding(0),out +RWStructuredBuffer<uint> gBuffer; + +[numthreads(4, 1, 1)] +void computeMain(uint3 dispatchThreadID : SV_DispatchThreadID) +{ + uint tid = dispatchThreadID.x; + + uint val = tid; + val = test(val); + + gBuffer[tid] = val; +} diff --git a/tests/bugs/gh-569.slang.expected.txt b/tests/bugs/gh-569.slang.expected.txt new file mode 100644 index 000000000..3195a6aa5 --- /dev/null +++ b/tests/bugs/gh-569.slang.expected.txt @@ -0,0 +1,4 @@ +4 +5 +6 +7 diff --git a/tests/compute/multiple-continue-sites.slang b/tests/compute/multiple-continue-sites.slang new file mode 100644 index 000000000..5a5b78d0c --- /dev/null +++ b/tests/compute/multiple-continue-sites.slang @@ -0,0 +1,39 @@ +//TEST(compute):COMPARE_COMPUTE: +//TEST_INPUT:ubuffer(data=[0 1 2 3], stride=4):dxbinding(0),glbinding(0),out + +// Test that a loop with multiple `continue` sites works. +// +// The current Slang codegen strategy for `continue` ends +// up duplicating the "continue clause" for a `for` loop +// at each `continue` site, so it will stress-test any +// code that assumes a given instruction/block only +// appears once in the region tree. +// + +int test(int inVal) +{ + int ii = inVal; + for(;!(ii & 0x20); ii += 0x10) + { + if(ii == 2) + { + continue; + } + + ii += 0x100; + // there is an implicit `continue` here + } + + return ii; +} + +RWStructuredBuffer<int> outputBuffer : register(u0); + +[numthreads(4, 1, 1)] +void computeMain(uint3 dispatchThreadID : SV_DispatchThreadID) +{ + uint tid = dispatchThreadID.x; + int inVal = outputBuffer[tid]; + int outVal = test(inVal); + outputBuffer[tid] = outVal; +}
\ No newline at end of file diff --git a/tests/compute/multiple-continue-sites.slang.expected.txt b/tests/compute/multiple-continue-sites.slang.expected.txt new file mode 100644 index 000000000..6752a80e0 --- /dev/null +++ b/tests/compute/multiple-continue-sites.slang.expected.txt @@ -0,0 +1,4 @@ +220 +221 +122 +223 diff --git a/tools/render-test/d3d-util.cpp b/tools/render-test/d3d-util.cpp index 5cc0dc69b..fb3cb49bf 100644 --- a/tools/render-test/d3d-util.cpp +++ b/tools/render-test/d3d-util.cpp @@ -269,7 +269,6 @@ bool D3DUtil::isTypeless(DXGI_FORMAT format) ::fputs((const char*)errorBlob->GetBufferPointer(), stderr); ::fflush(stderr); ::OutputDebugStringA((const char*)errorBlob->GetBufferPointer()); - return SLANG_FAIL; } SLANG_RETURN_ON_FAIL(hr); |