Add a warning on missing return, and initial SCCP pass (#671)

* Add a warning on missing return, and initial SCCP pass

The user-visible feature added here is a diagnostic for functions with non-`void` return type where control flow might fall off the end. This *sounds* like a trivial diagnostic to add as part of the front-end AST checking, but that can run afoul of really basic stuff like:

```hlsl
int thisFunctionisOkay(int a)
{
    while(true)
    {
        if(a > 10) return a;
        a = a*2 + 1;
    }
    // no return here!
}
```

This function "obviously" doesn't need to have a `return` statement at the end there, but realizing this fact relies on the compiler to understand that the `while(true)` loop can't exit normally, and doesn't contain any `break` statement. One can write "obvious" examples that need more and more complex analysis to rule out.

The answer Slang uses for stuff like this is to do the analysis at the IR level right after initial code generation (this would be before serialization, BTW, so that attached `IRHighLevelDeclDecoration`s can be used).

When lowering the AST to the IR, we always emit a `missingReturn` instruction (a subtype of `IRUnreachable`) at the end of its body if it isn't already terminated. The IR analysis pass to detect missing `return` statements is then as simple as just walking through all the functions in the module and making sure they don't contain `missingReturn` instructions.

For that simple pass to work, we first need to make some effort to remove dead blocks that control flow can never reach. This change adds a very basic initial implementation of Spare Conditional Constant Propagation (SCCP), which is a well-known SSA optimization that combines constant propagation over SSA form with dead code elimination over a CFG to achieve optimizations that are not possible with either optimization along.

For the moment, we don't actually implement any constant *folding* as part of the SCCP pass, so we can eliminate the dead block in a case like the function above (and those in the test case added in this change), but will not catch things like a `while(0 < 1)` loop. Handling more "obvious" cases like that is left for future work.

* fixup: warning on unreachable code

* Handle case where user of an inst isn't in same function/code

The code as assuming any instruction in the SSA work list has to come from the function/code being processed, but this misses the case where an instruction in a generic has a use inside the function that the generic produces.

This change adds code to guard against that case.

1 files changed, 87 insertions, 13 deletions

diff --git a/source/slang/ir.cpp b/source/slang/ir.cpp
index 0b4427f35..3ba2aa0dd 100644
--- a/source/slang/ir.cpp
+++ b/source/slang/ir.cpp
@@ -319,7 +319,8 @@ namespace Slang
         {
         case kIROp_ReturnVal:
         case kIROp_ReturnVoid:
-        case kIROp_unreachable:
+        case kIROp_Unreachable:
+        case kIROp_MissingReturn:
         case kIROp_discard:
             break;
 
@@ -337,7 +338,7 @@ namespace Slang
             end = begin + 2;
             break;
 
-        case kIROp_switch:
+        case kIROp_Switch:
             // switch <val> <break> <default> <caseVal1> <caseBlock1> ...
             begin = operands + 2;
 
@@ -423,6 +424,12 @@ namespace Slang
         return count;
     }
 
+    bool IRBlock::PredecessorList::isEmpty()
+    {
+        return !(begin() != end());
+    }
+
+
     void IRBlock::PredecessorList::Iterator::operator++()
     {
         if (!use) return;
@@ -471,6 +478,43 @@ namespace Slang
         return (IRBlock*)use->get();
     }
 
+    UInt IRUnconditionalBranch::getArgCount()
+    {
+        switch(op)
+        {
+        case kIROp_unconditionalBranch:
+            return getOperandCount() - 1;
+
+        case kIROp_loop:
+            return getOperandCount() - 3;
+
+        default:
+            SLANG_UNEXPECTED("unhandled unconditional branch opcode");
+            UNREACHABLE_RETURN(0);
+        }
+    }
+
+    IRUse* IRUnconditionalBranch::getArgs()
+    {
+        switch(op)
+        {
+        case kIROp_unconditionalBranch:
+            return getOperands() + 1;
+
+        case kIROp_loop:
+            return getOperands() + 3;
+
+        default:
+            SLANG_UNEXPECTED("unhandled unconditional branch opcode");
+            UNREACHABLE_RETURN(0);
+        }
+    }
+
+    IRInst* IRUnconditionalBranch::getArg(UInt index)
+    {
+        return getArgs()[index].usedValue;
+    }
+
     IRParam* IRGlobalValueWithParams::getFirstParam()
     {
         auto entryBlock = getFirstBlock();
@@ -506,8 +550,9 @@ namespace Slang
         case kIROp_loop:
         case kIROp_ifElse:
         case kIROp_discard:
-        case kIROp_switch:
-        case kIROp_unreachable:
+        case kIROp_Switch:
+        case kIROp_Unreachable:
+        case kIROp_MissingReturn:
             return true;
         }
     }
@@ -1162,7 +1207,7 @@ namespace Slang
         }
         switch (op)
         {
-            case kIROp_boolConst:
+            case kIROp_BoolLit:
             case kIROp_FloatLit:
             case kIROp_IntLit:
             {
@@ -1188,7 +1233,7 @@ namespace Slang
 
         switch (op)
         {
-            case kIROp_boolConst:
+            case kIROp_BoolLit:
             case kIROp_FloatLit:
             case kIROp_IntLit:
             {
@@ -1236,7 +1281,7 @@ namespace Slang
 
         switch (keyInst.op)
         {
-            case kIROp_boolConst:
+            case kIROp_BoolLit:
             case kIROp_IntLit:
             {
                 irValue = static_cast<IRConstant*>(createInstWithSizeImpl(builder, keyInst.op, keyInst.getFullType(), prefixSize + sizeof(IRIntegerValue)));
@@ -1284,7 +1329,7 @@ namespace Slang
     {
         IRConstant keyInst;
         memset(&keyInst, 0, sizeof(keyInst));
-        keyInst.op = kIROp_boolConst;
+        keyInst.op = kIROp_BoolLit;
         keyInst.typeUse.usedValue = getBoolType();
         keyInst.value.intVal = IRIntegerValue(inValue);
         return findOrEmitConstant(this, keyInst);
@@ -2320,7 +2365,17 @@ namespace Slang
     {
         auto inst = createInst<IRUnreachable>(
             this,
-            kIROp_unreachable,
+            kIROp_Unreachable,
+            nullptr);
+        addInst(inst);
+        return inst;
+    }
+
+    IRInst* IRBuilder::emitMissingReturn()
+    {
+        auto inst = createInst<IRMissingReturn>(
+            this,
+            kIROp_MissingReturn,
             nullptr);
         addInst(inst);
         return inst;
@@ -2444,7 +2499,7 @@ namespace Slang
 
         auto inst = createInstWithTrailingArgs<IRSwitch>(
             this,
-            kIROp_switch,
+            kIROp_Switch,
             nullptr,
             fixedArgCount,
             fixedArgs,
@@ -2741,7 +2796,7 @@ namespace Slang
             dump(context, ((IRConstant*)inst)->value.floatVal);
             return;
 
-        case kIROp_boolConst:
+        case kIROp_BoolLit:
             dump(context, ((IRConstant*)inst)->value.intVal ? "true" : "false");
             return;
         case kIROp_StringLit:
@@ -3092,7 +3147,7 @@ namespace Slang
         {
         case kIROp_IntLit:
         case kIROp_FloatLit:
-        case kIROp_boolConst:
+        case kIROp_BoolLit:
         case kIROp_StringLit:
             dumpOperand(context, inst);
             break;
@@ -3409,10 +3464,29 @@ namespace Slang
         removeFromParent();
         removeArguments();
 
+        // If this is a parent instruction then we had
+        // better remove all its children as well.
+        //
+        if(auto parentInst = as<IRParentInst>(this))
+        {
+            parentInst->removeAndDeallocateAllChildren();
+        }
+
         // Run destructor to be sure...
         this->~IRInst();
     }
 
+    void IRParentInst::removeAndDeallocateAllChildren()
+    {
+        IRInst* nextChild = nullptr;
+        for( IRInst* child = getFirstChild(); child; child = nextChild )
+        {
+            nextChild = child->getNextInst();
+            child->removeAndDeallocate();
+        }
+    }
+
+
     bool IRInst::mightHaveSideEffects()
     {
         // TODO: We should drive this based on flags specified
@@ -5311,7 +5385,7 @@ namespace Slang
 
         switch (originalValue->op)
         {
-        case kIROp_boolConst:
+        case kIROp_BoolLit:
             {
                 IRConstant* c = (IRConstant*)originalValue;
                 return builder->getBoolValue(c->value.intVal != 0);