From d3c1c8b5a80d7ae72678ae209b5c0a7a7053ae2a Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Wed, 2 May 2018 06:45:35 -0700 Subject: Fix emit logic when "terminators" occur in the middle of a block (#540) Fixes #527 There were a few problem cases for the IR emit logic. The most obvious, which came up in #527 is that a function body with multiple `return` statements would generate invalid code: ```hlsl int foo() { return 1; int x = 2; return x; } ``` In that case the IR for `foo` would have a single block that has two `return` instructions, which is invalid. Another case that seems to be arising more often, but that had less obvious consequences was when one arm of an `if` statement ends in a `return`: ```hlsl if(a) { return b; } else { int c = 0; } int d = 0; ``` In that case, the `return` instruction for `return b` would be followed by a branch to the end of the `if` (the `int d = 0;` line), because that would be the normal control flow without the early `return`. The fix implemented here is to have the IR lowering logic be a bit more careful on two fronts: 1. When emitting a branch, check if the block we are emitting into has already been terminated, and if so just don't emit the branch (since we are logically at an unreachable point in the CFG. 2. Whenever we are about to emit code for a (non-empty) statement, ensure that the current block being build is unterminated. If the current block is terminated, then start a new one. Case (2) will only matter when there is unreachable code (e.g., in the function `foo()`, the declaration of `x` and the second `return` can never be reached), so I added a warning in that case, and included a test case that triggers the new warning (with a function like `foo()` above). --- source/slang/diagnostic-defs.h | 5 ++ source/slang/ir-validate.cpp | 15 ++++++ source/slang/lower-to-ir.cpp | 102 ++++++++++++++++++++++++++++++++++++----- 3 files changed, 110 insertions(+), 12 deletions(-) (limited to 'source') diff --git a/source/slang/diagnostic-defs.h b/source/slang/diagnostic-defs.h index 0dbacafe0..8f564cc59 100644 --- a/source/slang/diagnostic-defs.h +++ b/source/slang/diagnostic-defs.h @@ -303,6 +303,11 @@ DIAGNOSTIC(40006, Error, needCompileTimeConstant, "expected a compile-time const DIAGNOSTIC(40007, Internal, irValidationFailed, "IR validation failed: $0") +// 41000 - IR-level validation issues + +DIAGNOSTIC(41000, Warning, unreachableCode, "unreachable code detected") + + // // 5xxxx - Target code generation. // diff --git a/source/slang/ir-validate.cpp b/source/slang/ir-validate.cpp index 7c04c0873..1f5112a51 100644 --- a/source/slang/ir-validate.cpp +++ b/source/slang/ir-validate.cpp @@ -48,6 +48,21 @@ namespace Slang // Recursively validate the instruction itself. validateIRInst(context, child); + // Do some extra validation around terminator instructions: + // + // * The last instruction of a block should always be a terminator + // * No other instruction should be a terminator + // + if(as(parent) && (child == parent->getLastChild())) + { + validate(context, as(child) != nullptr, child, "last instruction in block must be terminator"); + } + else + { + validate(context, !as(child), child, "terminator must be last instruction in a block"); + } + + prevChild = child; } } diff --git a/source/slang/lower-to-ir.cpp b/source/slang/lower-to-ir.cpp index fffd8acf3..371c68809 100644 --- a/source/slang/lower-to-ir.cpp +++ b/source/slang/lower-to-ir.cpp @@ -360,6 +360,11 @@ struct IRGenContext { return shared->compileRequest; } + + DiagnosticSink* getSink() + { + return &getCompileRequest()->mSink; + } }; void setGlobalValue(SharedIRGenContext* sharedContext, Decl* decl, LoweredValInfo value) @@ -2049,9 +2054,35 @@ struct StmtLoweringVisitor : StmtVisitor return getBuilder()->createBlock(); } - // Insert a block at the current location (ending - // the previous block with an unconditional jump - // if needed). + /// Does the given block have a terminator? + bool isBlockTerminated(IRBlock* block) + { + return block->getTerminator() != nullptr; + } + + /// Emit a branch to the target block if the current + /// block being inserted into is not already terminated. + void emitBranchIfNeeded(IRBlock* targetBlock) + { + auto builder = getBuilder(); + auto currentBlock = builder->getBlock(); + + // Don't emit if there is no current block. + if(!currentBlock) + return; + + // Don't emit if the block already has a terminator. + if(isBlockTerminated(currentBlock)) + return; + + // The block is unterminated, so cap it off with + // a terminator that branches to the target. + builder->emitBranch(targetBlock); + } + + /// Insert a block at the current location (ending + /// the previous block with an unconditional jump + /// if needed). void insertBlock(IRBlock* block) { auto builder = getBuilder(); @@ -2062,13 +2093,11 @@ struct StmtLoweringVisitor : StmtVisitor // If the previous block doesn't already have // a terminator instruction, then be sure to // emit a branch to the new block. - if (prevBlock && !prevBlock->getTerminator()) - { - builder->emitBranch(block); - } + emitBranchIfNeeded(block); + // Add the new block to the function we are building, + // and setit as the block we will be inserting into. parentFunc->addBlock(block); - builder->setInsertInto(block); } @@ -2082,9 +2111,43 @@ struct StmtLoweringVisitor : StmtVisitor return block; } + /// Start a new block if there isn't a current + /// block that we can append to. + /// + /// The `stmt` parameter is the statement we + /// are about to emit. + void startBlockIfNeeded(Stmt* stmt) + { + auto builder = getBuilder(); + auto currentBlock = builder->getBlock(); + + // If there is a current block and it hasn't + // been terminated, then we can just use that. + if(currentBlock && !isBlockTerminated(currentBlock)) + { + return; + } + + // We are about to emit code *after* a terminator + // instruction, and there is no label to allow + // branching into this code, so whatever we are + // about to emit is going to be unreachable. + // + // Let's diagnose that here just to help the user. + // + // TODO: We might want to have a more robust check + // for unreachable code based on IR analysis instead, + // at which point we'd probably disable this check. + // + context->getSink()->diagnose(stmt, Diagnostics::unreachableCode); + + startBlock(); + } + void visitIfStmt(IfStmt* stmt) { auto builder = getBuilder(); + startBlockIfNeeded(stmt); auto condExpr = stmt->Predicate; auto thenStmt = stmt->PositiveStatement; @@ -2103,7 +2166,7 @@ struct StmtLoweringVisitor : StmtVisitor insertBlock(thenBlock); lowerStmt(context, thenStmt); - builder->emitBranch(afterBlock); + emitBranchIfNeeded(afterBlock); insertBlock(elseBlock); lowerStmt(context, elseStmt); @@ -2139,6 +2202,7 @@ struct StmtLoweringVisitor : StmtVisitor void visitForStmt(ForStmt* stmt) { auto builder = getBuilder(); + startBlockIfNeeded(stmt); // The initializer clause for the statement // can always safetly be emitted to the current block. @@ -2199,7 +2263,7 @@ struct StmtLoweringVisitor : StmtVisitor } // At the end of the body we need to jump back to the top. - builder->emitBranch(loopHead); + emitBranchIfNeeded(loopHead); // Finally we insert the label that a `break` will jump to insertBlock(breakLabel); @@ -2211,6 +2275,7 @@ struct StmtLoweringVisitor : StmtVisitor // `for` statement, but without a lot of the complications. auto builder = getBuilder(); + startBlockIfNeeded(stmt); // We will create blocks for the various places // we need to jump to inside the control flow, @@ -2260,7 +2325,7 @@ struct StmtLoweringVisitor : StmtVisitor lowerStmt(context, stmt->Statement); // At the end of the body we need to jump back to the top. - builder->emitBranch(loopHead); + emitBranchIfNeeded(loopHead); // Finally we insert the label that a `break` will jump to insertBlock(breakLabel); @@ -2272,6 +2337,7 @@ struct StmtLoweringVisitor : StmtVisitor // `while` statement, just with the test in a different place auto builder = getBuilder(); + startBlockIfNeeded(stmt); // We will create blocks for the various places // we need to jump to inside the control flow, @@ -2328,6 +2394,8 @@ struct StmtLoweringVisitor : StmtVisitor void visitExpressionStmt(ExpressionStmt* stmt) { + startBlockIfNeeded(stmt); + // The statement evaluates an expression // (for side effects, one assumes) and then // discards the result. As such, we simply @@ -2343,6 +2411,8 @@ struct StmtLoweringVisitor : StmtVisitor void visitDeclStmt(DeclStmt* stmt) { + startBlockIfNeeded(stmt); + // For now, we lower a declaration directly // into the current context. // @@ -2376,6 +2446,8 @@ struct StmtLoweringVisitor : StmtVisitor void visitReturnStmt(ReturnStmt* stmt) { + startBlockIfNeeded(stmt); + // A `return` statement turns into a return // instruction. If the statement had an argument // expression, then we need to lower that to @@ -2392,13 +2464,16 @@ struct StmtLoweringVisitor : StmtVisitor } } - void visitDiscardStmt(DiscardStmt* /*stmt*/) + void visitDiscardStmt(DiscardStmt* stmt) { + startBlockIfNeeded(stmt); getBuilder()->emitDiscard(); } void visitBreakStmt(BreakStmt* stmt) { + startBlockIfNeeded(stmt); + // Semantic checking is responsible for finding // the statement taht this `break` breaks out of auto parentStmt = stmt->parentStmt; @@ -2415,6 +2490,8 @@ struct StmtLoweringVisitor : StmtVisitor void visitContinueStmt(ContinueStmt* stmt) { + startBlockIfNeeded(stmt); + // Semantic checking is responsible for finding // the loop that this `continue` statement continues auto parentStmt = stmt->parentStmt; @@ -2575,6 +2652,7 @@ struct StmtLoweringVisitor : StmtVisitor void visitSwitchStmt(SwitchStmt* stmt) { auto builder = getBuilder(); + startBlockIfNeeded(stmt); // Given a statement: // -- cgit v1.2.3