Preliminary Liveness tracking (#2218)

* #include an absolute path didn't work - because paths were taken to always be relative.

* WIP tracking liveness.

* Skeleton around adding liveness instructions.

* Calling into liveness tracking logic.
Adds live start to var insts.

* Liveness macros have initial output.

* Looking at different initialization scenarios.

* Some discussion around liveness.

* WIP for working out liveness end.

* WIP Updated liveness using use lists.

* Is now adding liveness information

* Some small fixes.

* WIP around liveness.

* Seems to output liveness correctly for current scenario.

* Tidy up liveness code.

* Update comment arounds liveness to current status.

* Small fixes to liveness test.

* Add support for call in liveness analysis.

* Improve liveness example with array access.

* Small updates to comments.

* Disable liveness test because inconsistencies with output on CI system.

* Fix some issues brought up in PR.

* Rename liveness instructions.

14 files changed, 901 insertions, 3 deletions

diff --git a/source/slang/slang-compiler.cpp b/source/slang/slang-compiler.cpp
index 4445d9620..7988af3e8 100644
--- a/source/slang/slang-compiler.cpp
+++ b/source/slang/slang-compiler.cpp
@@ -2509,6 +2509,14 @@ void printDiagnosticArg(StringBuilder& sb, CodeGenTarget val)
         return false;
     }
 
+
+    bool CodeGenContext::shouldTrackLiveness()
+    {
+        auto endToEndReq = isEndToEndCompile();
+        return (endToEndReq && endToEndReq->enableLivenessTracking) || 
+            getTargetReq()->shouldTrackLiveness();
+    }
+
     String CodeGenContext::getIntermediateDumpPrefix()
     {
         if (auto endToEndReq = isEndToEndCompile())
diff --git a/source/slang/slang-compiler.h b/source/slang/slang-compiler.h
index d534e986a..a9a19d29c 100755
--- a/source/slang/slang-compiler.h
+++ b/source/slang/slang-compiler.h
@@ -1485,6 +1485,10 @@ namespace Slang
 
         bool shouldDumpIntermediates() { return dumpIntermediates; }
 
+        void setTrackLiveness(bool enable) { enableLivenessTracking = enable; }
+
+        bool shouldTrackLiveness() { return enableLivenessTracking; }
+
         Linkage* getLinkage() { return linkage; }
         CodeGenTarget getTarget() { return format; }
         Profile getTargetProfile() { return targetProfile; }
@@ -1515,6 +1519,7 @@ namespace Slang
         LineDirectiveMode       lineDirectiveMode = LineDirectiveMode::Default;
         bool                    dumpIntermediates = false;
         bool                    forceGLSLScalarBufferLayout = false;
+        bool                    enableLivenessTracking = false;
     };
 
         /// Are we generating code for a D3D API?
@@ -2368,6 +2373,8 @@ namespace Slang
         bool shouldValidateIR();
         bool shouldDumpIR();
 
+        bool shouldTrackLiveness();
+
         bool shouldDumpIntermediates();
         String getIntermediateDumpPrefix();
 
@@ -2652,6 +2659,7 @@ namespace Slang
 
         void generateOutput();
 
+        void setTrackLiveness(bool enable);
 
         // Note: The following settings used to be considered part of the "back-end" compile
         // request, but were only being used as part of end-to-end compilation anyway,
@@ -2661,6 +2669,9 @@ namespace Slang
         // Should we dump intermediate results along the way, for debugging?
         bool shouldDumpIntermediates = false;
 
+        // True if liveness tracking is enabled
+        bool enableLivenessTracking = false;
+
         // Should R/W images without explicit formats be assumed to have "unknown" format?
         //
         // The default behavior is to make a best-effort guess as to what format is intended.
diff --git a/source/slang/slang-emit-c-like.cpp b/source/slang/slang-emit-c-like.cpp
index dccfde7b7..90ccb3e73 100644
--- a/source/slang/slang-emit-c-like.cpp
+++ b/source/slang/slang-emit-c-like.cpp
@@ -405,6 +405,43 @@ void CLikeSourceEmitter::emitType(IRType* type, NameLoc const& nameAndLoc)
     emitType(type, nameAndLoc.name, nameAndLoc.loc);
 }
 
+
+void CLikeSourceEmitter::emitLivenessImpl(IRInst* inst)
+{
+    
+    auto liveMarker = as<IRLiveRangeMarker>(inst);
+    if (!liveMarker)
+    {
+        return;
+    }
+
+    IRInst* referenced = liveMarker->getReferenced();
+    SLANG_ASSERT(referenced);
+
+    UnownedStringSlice text;
+    switch (inst->getOp())
+    {
+        case kIROp_LiveRangeStart:
+        {
+            text = UnownedStringSlice::fromLiteral("SLANG_LIVE_START");
+            break;
+        }
+        case kIROp_LiveRangeEnd:
+        {
+            text = UnownedStringSlice::fromLiteral("SLANG_LIVE_END");
+            break;
+        }
+        default: break;
+    }
+
+    m_writer->emit(text);
+    m_writer->emit("(");
+
+    emitOperand(referenced, getInfo(EmitOp::General));
+
+    m_writer->emit(")\n");
+}
+
 //
 // Expressions
 //
@@ -2029,6 +2066,10 @@ void CLikeSourceEmitter::_emitInst(IRInst* inst)
         m_writer->emit(";\n");
         break;
 
+    case kIROp_LiveRangeStart:
+    case kIROp_LiveRangeEnd:
+        emitLiveness(inst);
+        break;
     case kIROp_undefined:
     case kIROp_DefaultConstruct:
         {
diff --git a/source/slang/slang-emit-c-like.h b/source/slang/slang-emit-c-like.h
index ba2f5b86c..a74d874a7 100644
--- a/source/slang/slang-emit-c-like.h
+++ b/source/slang/slang-emit-c-like.h
@@ -309,6 +309,8 @@ public:
 
     void emitCallExpr(IRCall* inst, EmitOpInfo outerPrec);
 
+    void emitLiveness(IRInst* inst) { emitLivenessImpl(inst); }
+
     void emitInstExpr(IRInst* inst, EmitOpInfo const& inOuterPrec);
     void defaultEmitInstExpr(IRInst* inst, EmitOpInfo const& inOuterPrec);
     void diagnoseUnhandledInst(IRInst* inst);
@@ -465,6 +467,7 @@ public:
     virtual void emitFunctionPreambleImpl(IRInst* inst) { SLANG_UNUSED(inst); }
     virtual void emitLoopControlDecorationImpl(IRLoopControlDecoration* decl) { SLANG_UNUSED(decl); }
     virtual void emitFuncDecorationImpl(IRDecoration* decoration) { SLANG_UNUSED(decoration); }
+    virtual void emitLivenessImpl(IRInst* inst);
 
         // Only needed for glsl output with $ prefix intrinsics - so perhaps removable in the future
     virtual void emitTextureOrTextureSamplerTypeImpl(IRTextureTypeBase*  type, char const* baseName) { SLANG_UNUSED(type); SLANG_UNUSED(baseName); }
diff --git a/source/slang/slang-emit.cpp b/source/slang/slang-emit.cpp
index d09217b58..0f43762c1 100644
--- a/source/slang/slang-emit.cpp
+++ b/source/slang/slang-emit.cpp
@@ -38,6 +38,8 @@
 #include "slang-ir-union.h"
 #include "slang-ir-validate.h"
 #include "slang-ir-wrap-structured-buffers.h"
+#include "slang-ir-liveness.h"
+
 #include "slang-legalize-types.h"
 #include "slang-lower-to-ir.h"
 #include "slang-mangle.h"
@@ -484,9 +486,9 @@ Result linkAndOptimizeIR(
         {
             wrapStructuredBuffersOfMatrices(irModule);
 #if 0
-                dumpIRIfEnabled(codeGenContext, irModule, "STRUCTURED BUFFERS WRAPPED");
+            dumpIRIfEnabled(codeGenContext, irModule, "STRUCTURED BUFFERS WRAPPED");
 #endif
-                validateIRModuleIfEnabled(codeGenContext, irModule);
+            validateIRModuleIfEnabled(codeGenContext, irModule);
         }
         break;
 
@@ -728,6 +730,40 @@ Result linkAndOptimizeIR(
     lowerBitCast(targetRequest, irModule);
     simplifyIR(irModule);
 
+    // TODO(JS): We probably want to add a pass that moves phi-node temporaries to 
+    // IR.
+    // 
+    // Currently these are added as part of emit in
+    // emitPhiVarAssignments and emitPhiVarDecls
+    // 
+    // A possible mechanism might be:
+    // 1) Find all of the parameters passed between blocks
+    // 2) Make a variable for each one of them 
+    //    This could be at the scope for the function, or more ideally a scope that is 'most appropriate' for how the parameter is passed 
+    //    ie the closest scope such that the variable is in scope across the branch.
+    // 3) Replace all uses of the parameters passed into a block (except the entry block), with the temporary
+    // 3a) Remove the parameters from the start of a block (other than the entry block)
+    // 4) For all of the branches in a function
+    // 4a) For each parameter passed in the branch, assign to the temporary
+    // 4b) Replace the branch with a branch that has no parameters
+    //
+    // This should lead to an equivalent function, where the parameter passing between blocks is removed, and all the temporaries
+    // are explicit in the output.
+    // 
+    // I guess there could be a desire to combine the liveness tracking into this pass, because once a phi-temporary has been moved
+    // we have lost(?) information about liveness. That could potentially be recovered, but for the phi-temporaries, their 
+    // initial liveness is trivial, it's when the assignment takes place, at the branch point. 
+    // 
+    // If all the temporaries were marked as such, then this would be fairly trivial to recreate. 
+
+    // TODO(JS): Without a pass to make all variables (including phi ones), the liveness tracking can't track everything
+    if (codeGenContext->shouldTrackLiveness())
+    {
+        addLivenessTrackingToModule(irModule);
+
+        dumpIRIfEnabled(codeGenContext, irModule, "LIVENESS");
+    }
+
     // We include one final step to (optionally) dump the IR and validate
     // it after all of the optimization passes are complete. This should
     // reflect the IR that code is generated from as closely as possible.
diff --git a/source/slang/slang-ir-dominators.h b/source/slang/slang-ir-dominators.h
index f4ecd0cd0..be01830b0 100644
--- a/source/slang/slang-ir-dominators.h
+++ b/source/slang/slang-ir-dominators.h
@@ -85,6 +85,8 @@ namespace Slang
             Iterator begin() const;
             Iterator end() const;
 
+            Count getCount() const { return Count(mEnd - mBegin); }
+
         private:
             friend struct IRDominatorTree;
             DominatedList(
diff --git a/source/slang/slang-ir-inst-defs.h b/source/slang/slang-ir-inst-defs.h
index bce188cfa..d5cb49046 100644
--- a/source/slang/slang-ir-inst-defs.h
+++ b/source/slang/slang-ir-inst-defs.h
@@ -718,6 +718,11 @@ INST_RANGE(Layout, VarLayout, EntryPointLayout)
     INST_RANGE(LayoutResourceInfoAttr, TypeSizeAttr, VarOffsetAttr)
 INST_RANGE(Attr, PendingLayoutAttr, VarOffsetAttr)
 
+/* Liveness */
+    INST(LiveRangeStart, liveRangeStart, 2, 0)
+    INST(LiveRangeEnd, liveRangeEnd, 0, 0)
+INST_RANGE(LiveRangeMarker, LiveRangeStart, LiveRangeEnd)
+
 #undef PARENT
 #undef USE_OTHER
 #undef INST_RANGE
diff --git a/source/slang/slang-ir-insts.h b/source/slang/slang-ir-insts.h
index 717e1be59..96fe350f8 100644
--- a/source/slang/slang-ir-insts.h
+++ b/source/slang/slang-ir-insts.h
@@ -1807,6 +1807,43 @@ struct IRExtractExistentialWitnessTable : IRInst
     IR_LEAF_ISA(ExtractExistentialWitnessTable);
 };
 
+/* Base class for instructions that track liveness */
+struct IRLiveRangeMarker : IRInst
+{
+    IR_PARENT_ISA(LiveRangeMarker)
+
+    // TODO(JS): It might be useful to track how many bytes are live in the item referenced. 
+    // It's not entirely clear how that will work across different targets, or even what such a 
+    // size means on some targets.
+    // 
+    // Here we assume the size is the size of the type being referenced (whatever that means on a target)
+    //
+    // Potentially we could have a count, for defining (say) a range of an array. It's not clear this is 
+    // needed, so we just have the item referenced.
+
+        /// The referenced item whose liveness starts after this instruction
+    IRInst* getReferenced() { return getOperand(0); }
+};
+
+/// Identifies then the item references starts being live.
+struct IRLiveRangeStart : IRLiveRangeMarker
+{
+    IR_LEAF_ISA(LiveRangeStart);        
+};
+
+/// Demarks where the referenced item is no longer live, optimimally (although not
+/// necessarily) at the previous instruction. 
+/// 
+/// There *can* be acceses to the referenced item after the end, if those accesses
+/// can never be seen. For example if there is a store, without any subsequent loads, 
+/// the store will never be seen (by a load) and so can be ignored.
+///
+/// In general there can be one or more 'ends' for every start.
+struct IRLiveRangeEnd : IRLiveRangeMarker
+{
+    IR_LEAF_ISA(LiveRangeEnd);
+};
+
 // Description of an instruction to be used for global value numbering
 struct IRInstKey
 {
@@ -2167,6 +2204,12 @@ public:
         return getAttributedType(baseType, attributes.getCount(), attributes.getBuffer());
     }
 
+        /// Emit an LiveRangeStart instruction indicating the referenced item is live following this instruction
+    IRLiveRangeStart* emitLiveRangeStart(IRInst* referenced);
+
+        /// Emit a LiveRangeEnd instruction indicating the referenced item is no longer live when this instruction is reached.
+    IRLiveRangeEnd* emitLiveRangeEnd(IRInst* referenced);
+
     // Set the data type of an instruction, while preserving
     // its rate, if any.
     void setDataType(IRInst* inst, IRType* dataType);
diff --git a/source/slang/slang-ir-liveness.cpp b/source/slang/slang-ir-liveness.cpp
new file mode 100644
index 000000000..3d1626691
--- /dev/null
+++ b/source/slang/slang-ir-liveness.cpp
@@ -0,0 +1,533 @@
+#include "slang-ir-liveness.h"
+
+#include "slang-ir-insts.h"
+#include "slang-ir.h"
+
+#include "slang-ir-dominators.h"
+
+namespace Slang
+{
+
+
+/* 
+Discussion 
+==========
+
+Currently we are only tracking 'var'/IRVar local variables. They are accessed via pointers. This
+means
+
+* We don't need to care about extractField / extractElement, as they only work directly on the value
+* We need to track aliases created via getFieldPtr / getElementPtr
+* There is a distinction between a 'pointer' and an 'address'.
+  * A "pointer" can 'escape' just as in other languages, and is the general case
+  * If we are talking about an "address", then this is constrained by our language rules,
+  
+NOTE! Confusingly there is getElementPtr and getFieldAddress (and getAddress). I also don't see Addr/Addr type as a distinct thing 
+from Ptr, so I assume that differentiation is aspirational?
+
+A) We don't need to worry about a phi node temporary holding a pointer (or scope ending *on* the branch), because
+the phi node will pass the result by value, leading to a *load* before the branch..
+
+Other
+
+```
+ let foo : Ptr<SomeStruct> = var;
+...
+store(someOtherPtr, foo); // this is `store`, but not a store *to* foo!!!!!
+...
+```
+
+Here a *pointer* is being stored into someOtherPtr. This means all bets are off. Liveness will have to be assumed anywhere the 
+variable is accessible. 
+TODO(JS): Note that currently this scenario isn't handled by this algorithm.
+
+```
+   let foo : Ptr<SomeStruct> = var;
+   ...
+   br SomeOtherThing(foo); // OH NO!!!
+```
+
+It is believed this can't happen in current code. Leading to assertion A) above.
+
+* Long-term IR type-system thing: we should probably have an explicit instruction
+  that casts a local `Ptr<Foo>` to either an `Out<Foo>` or `InOut<Foo>` for exactly
+  these cases (and then use the *cast* operation to tell us what is going on).
+*/
+
+/*
+Take the code sequence
+
+```HLSL
+    SomeStruct s;
+    SomeStruct t = makeSomeStruct();
+    SomeStruct u = {};
+```
+
+Produces something like...
+
+```HLSL
+    SomeStruct_0 s_1;
+    SLANG_LIVE_START(s_1)
+    SomeStruct_0 t_0;
+    SLANG_LIVE_START(t_0)
+    SomeStruct_0 _S4 = makeSomeStruct_0();
+    t_0 = _S4;
+    SomeStruct_0 u_0;
+    SLANG_LIVE_START(u_0)
+    SomeStruct_0 _S6 = { ... };
+    u_0 = _S6;
+```
+
+This is good, in so far as the variables do get LIVE_START, however they are defined. It is perhaps 'bad' in so far as a temporary
+is created that is then just copied into the variable. That temporary being something that is mutable, and can be partially modified (it's a struct)
+could perhaps have liveness issues.
+*/
+
+namespace { // anonymous
+
+struct LivenessContext
+{
+    // NOTE! Care must be taken changing the order. Some checks rely on Found having a smaller value than `NotFound`.
+    // Allowing NotFound to be promoted to Found.
+    enum class FoundResult
+    {
+        Found,              ///< All paths were either not dominated, found 
+        NotFound,           ///< It is dominated but no access was found
+        NotDominated,       ///< If it's not dominated it can't have a liveness end 
+    };
+
+    enum class AccessType
+    {
+        None,               ///< There is no access
+        Alias,              ///< Produces an alias to the root
+        Access,             ///< Is an access to the root (perhaps through an alias)
+    };
+
+    struct RootInfo
+    {
+        IRInst* root;
+        IRLiveRangeStart* liveStart;
+    };
+
+        /// Processor a successor to a block
+    FoundResult processSuccessor(IRBlock* block);
+
+        /// Process a block 
+    FoundResult processBlock(IRBlock* block);
+
+        /// Process a 'root'. A variable that has liveness tracking
+    void processRoot(const RootInfo& rootInfo);
+
+        /// Process a function in the module
+    void processFunction(IRFunc* funcInst);
+
+        /// Process the module
+    void processModule();
+
+    LivenessContext(IRModule* module):
+        m_module(module)
+    {
+        m_sharedBuilder.init(module);
+        m_builder.init(m_sharedBuilder);
+    }
+
+        // Add a live end instruction at the start of block, referencing the root 'root'.
+    void _addLiveRangeEndAtBlockStart(IRBlock* block, IRInst* root);
+
+        /// Find the last instruction in block that accesses one of the roots or it's aliases
+        /// Requires that m_accessSet contains all of the accesses
+        /// Returns nullptr if no access instruction was found in the block.
+    IRInst* _findLastAccessInBlock(IRBlock* block);
+
+        /// Add a result for the block
+        /// Allows for promotion from NotFound -> Found if there is already a result
+    FoundResult _addResult(IRBlock* block, FoundResult result);
+
+    RefPtr<IRDominatorTree> m_dominatorTree;    ///< The dominator tree for the current function
+
+    IRInst* m_root;                             ///< The root item we are searching for accesses to, to determine scope/liveness
+    IRBlock* m_rootBlock;                       ///< The block the root is in
+    
+    HashSet<IRInst*> m_accessSet;               ///< Holds a set of all the functions that in some way access the root.
+
+    List<IRInst*> m_aliases;                    ///< A list of instructions that alias to the root
+
+    Dictionary<IRBlock*, FoundResult> m_blockResult;    ///< Cached result for each block
+
+    IRModule* m_module;
+    SharedIRBuilder m_sharedBuilder;
+    IRBuilder m_builder;
+};
+
+void LivenessContext::_addLiveRangeEndAtBlockStart(IRBlock* block, IRInst* root)
+{
+    // Insert before the first ordinary inst
+    auto inst = block->getFirstOrdinaryInst();
+    SLANG_ASSERT(inst);
+
+    m_builder.setInsertLoc(IRInsertLoc::before(inst));
+
+    // Add the live end inst
+    m_builder.emitLiveRangeEnd(root);
+}
+
+IRInst* LivenessContext::_findLastAccessInBlock(IRBlock* block)
+{
+    // Search the instructions in this block in reverse order, to find first access
+    for (IRInst* cur = block->getLastChild(); cur; cur = cur->getPrevInst())
+    {
+        if (m_accessSet.Contains(cur))
+        {
+            return cur;
+        }
+    }
+    return nullptr;
+}
+
+LivenessContext::FoundResult LivenessContext::_addResult(IRBlock* block, FoundResult result)
+{
+    auto currentResultPtr = m_blockResult.TryGetValueOrAdd(block, result);
+    if (currentResultPtr)
+    {
+        const auto currentResult = *currentResultPtr;
+        // If it were NotDominated, it cannot be promoted to Found/NotFound.
+        SLANG_ASSERT(currentResult != FoundResult::NotDominated);
+
+        // We can only promote from NotFound -> Found
+
+        SLANG_ASSERT(Index(result) <= Index(currentResult));
+
+        // Set the new result
+        *currentResultPtr = result;
+    }
+
+    return result;
+}
+
+LivenessContext::FoundResult LivenessContext::processSuccessor(IRBlock* block)
+{
+    // Check if there is already a result for this block. 
+    // If there is just return that.
+    auto res = m_blockResult.TryGetValue(block);
+    if (res)
+    {
+        return *res;
+    }
+
+    // If the block is *not* dominated by the root block, we know it can't 
+    // end liveness. 
+    // Return that it is not dominated, and add to the cache for the block
+    if (!m_dominatorTree->properlyDominates(m_rootBlock, block))
+    {
+        return _addResult(block, FoundResult::NotDominated);
+    }
+
+    // Else process the block to try and find the last used instruction
+    return processBlock(block);
+}
+
+LivenessContext::FoundResult LivenessContext::processBlock(IRBlock* block)
+{
+    // Find all the successors for this block
+    auto successors = block->getSuccessors();
+    const Index count = successors.getCount();
+
+    // We need to store of the results for successors
+    List<FoundResult> successorResults;
+    successorResults.setCount(count);
+
+    Index foundCount = 0;
+    Index notDominatedCount = 0;
+
+    {
+        auto cur = successors.begin();
+        for (Index i = 0; i < count; ++i, ++cur)
+        {
+            auto succ = *cur;
+
+            // Process the successor
+            const auto successorResult = processSuccessor(succ);
+
+            // Store the result
+            successorResults[i] = successorResult;
+
+            // Change counts depending on the result
+            foundCount += Index(successorResult == FoundResult::Found);
+            notDominatedCount += Index(successorResult == FoundResult::NotDominated);
+        }
+    }
+
+    // If one or more of the successors (or successors of successors),
+    // was found to have the last access, we need to mark the end of scope
+    // at the start of any other paths (which are dominated).
+    if (foundCount > 0)
+    {
+        // If all successors have result, or are not dominated
+        if (foundCount + notDominatedCount == count)
+        {
+            return _addResult(block, FoundResult::Found);
+        }
+
+        // We want to place an end scope in all blocks where it wasn't found
+        auto cur = successors.begin();
+        for (Index i = 0; i < count; ++i, ++cur)
+        {
+            auto successor = *cur;
+            const auto successorResult = successorResults[i];
+            if (successorResult == FoundResult::NotFound)
+            {
+                _addLiveRangeEndAtBlockStart(successor, m_root);
+                _addResult(successor, FoundResult::Found);
+            }
+        }
+
+        // This block, can be marked as found as all successors are either not dominated, found 
+        // or have have 
+        return _addResult(block, FoundResult::Found);
+    }
+
+    // Search the instructions in this block in reverse order, to find first access
+    IRInst* lastAccess = _findLastAccessInBlock(block);
+
+    // Wasn't an access so we are done
+    if (lastAccess == nullptr)
+    {
+        return _addResult(block, FoundResult::NotFound);
+    }
+
+    // Can never be a terminator, because logic to find the access instructions does not 
+    // include terminators.
+    SLANG_ASSERT(as<IRTerminatorInst>(lastAccess) == nullptr);
+
+    // Just add end of scope after the inst 
+    m_builder.setInsertLoc(IRInsertLoc::after(lastAccess));
+
+    // Add the live end inst
+    m_builder.emitLiveRangeEnd(m_root);
+    return _addResult(block, FoundResult::Found);
+}
+
+void LivenessContext::processRoot(const RootInfo& rootInfo)
+{
+    // Clear the work structures
+    m_accessSet.Clear();
+    m_aliases.clear();
+    m_blockResult.Clear();
+
+    auto root = rootInfo.root;
+
+    // Store root information, so don't have to pass around methods
+    m_rootBlock = as<IRBlock>(root->parent);
+    m_root = root;
+
+    // Add the root to the list of aliases, to start lookup
+    m_aliases.add(root);
+
+    // The challenge here is to try and determine when a root is no longer accessed, and so is no longer live
+    //
+    // Note that a root can be accessed directly, but also through `aliases`. For example if the root is a structure
+    // a pointer to a field in the root would be an alias.
+    // 
+    // In terms of liveness, the only accesses that are important are loads. This is because if the last operation on 
+    // a root/alias is a store, if it is never read it will never be seen, so in effect doesn't matter.
+    //
+    // The algorithm here works as follows
+    // 0) Prior to this function, a dominator tree is built for the function
+    //    This is usefuly because variables defined in block A, is only accessible to blocks *dominated* by A
+    // 1) Deterime all of the aliases, and accesses to the root
+    //    Add all the access instructions into m_accessSet
+    //    Add all the aliases to m_aliases
+
+    for (Index i = 0; i < m_aliases.getCount(); ++i)
+    {
+        IRInst* alias = m_aliases[i];
+
+        // Find all the uses of this alias/root
+        for (IRUse* use = alias->firstUse; use; use = use->nextUse)
+        {
+            IRInst* cur = use->getUser();
+            IRInst* base = nullptr;
+
+            IRBlock* block = as<IRBlock>(cur->getParent());
+            if (!block)
+            {
+                continue;
+            }
+
+            AccessType accessType = AccessType::None;
+
+            // We want to find instructions that access the root
+            switch (cur->getOp())
+            {
+            
+            case kIROp_getElementPtr:
+            {
+                base = static_cast<IRGetElementPtr*>(cur)->getBase();
+                accessType = AccessType::Alias;
+                break;
+            }
+            case kIROp_FieldAddress:
+            {
+                base = static_cast<IRFieldAddress*>(cur)->getBase();
+                accessType = AccessType::Alias;
+                break;
+            }
+            case kIROp_getAddr:
+            {
+                IRGetAddress* getAddr = static_cast<IRGetAddress*>(cur);
+                base = getAddr->getOperand(0);
+                accessType = AccessType::Alias;
+                break;
+            }
+            case kIROp_Call:
+            {
+                // TODO(JS): This is arguably too conservative. 
+                // 
+                // Depending on how the parameter is used - in, out, inout changes the interpretation
+                // 
+                // *If we are talking about a real "pointer" then this is basically the general case again.
+                //     the callee  could store  the pointer into a global, dictionary, whatever.
+                //
+                // * If we are talking about an "address", then this is constrained by our language rules,
+                //    and we kind of need to find the type of the matching parameter :
+                //   * If the parameter is an `out` parameter, this is basically like a `store`
+                //   * If the parameter is an `inout` parameter, this is basically like a `load`
+
+                // We can assume it accesses the base
+                base = alias;
+                accessType = AccessType::Access;
+                break;
+            }
+            case kIROp_Load:
+            {
+                // We only care about loads in terms of identifying liveness
+                base = static_cast<IRLoad*>(cur)->getPtr();
+                accessType = AccessType::Access;
+                break;
+            }
+            case kIROp_Store:
+            {
+                // In terms of liveness, stores can be ignored
+                break;
+            }
+            case kIROp_getElement:
+            case kIROp_FieldExtract:
+            {
+                // These will never take place on the var which is accessed through a pointer, so can be ignored
+                break;
+            }
+            default: break;
+            }
+
+            // Make sure the access is through the alias (as opposed to some other part of the instructions 'use')
+            if (base == alias)
+            {
+                switch (accessType)
+                {
+                case AccessType::Alias:
+                {
+                    // Add this instruction to the aliases
+                    m_aliases.add(cur);
+                    break;
+                }
+                case AccessType::Access:
+                {
+                    m_accessSet.Add(cur);
+                    break;
+                }
+                default: break;
+                }
+            }
+        }
+    }
+
+    // Now we want to find the last access in the graph of successors
+    //
+    // This works by recursively starting from the block where the variable is defined, walking depth first the graph of 
+    // successors. We cache the results in m_blockResult
+    //
+    // There is an extra caveat around the dominator tree. If we just traversed the successors, if there is a loop
+    // we'd end up in an infinite loop. We can avoid this because we know that the root is only available in blocks dominated
+    // by the root. 
+
+    {
+        auto foundResult = processBlock(m_rootBlock);
+
+        if (foundResult == FoundResult::NotFound)
+        {
+            // Means there is no access to this variable(!)
+            // Which means we can end the scope, after the the start scope
+            m_builder.setInsertLoc(IRInsertLoc::after(rootInfo.liveStart));
+            m_builder.emitLiveRangeEnd(root);
+        }
+    }
+}
+
+void LivenessContext::processFunction(IRFunc* funcInst)
+{
+    List<RootInfo> rootInfos;
+
+    // Iterate through blocks in the function, looking for variables to live track
+    for (auto block = funcInst->getFirstBlock(); block; block = block->getNextBlock())
+    {
+        for (auto inst = block->getFirstChild(); inst; inst = inst->getNextInst())
+        {
+            // We look for var declarations.
+            if (auto varInst = as<IRVar>(inst))
+            {
+                // Add the start location
+                m_builder.setInsertLoc(IRInsertLoc::after(varInst));
+
+                // Emit the start
+                auto liveStart = m_builder.emitLiveRangeStart(varInst);
+
+                // Add as a root
+                RootInfo rootInfo;
+                rootInfo.root = varInst;
+                rootInfo.liveStart = liveStart;
+
+                rootInfos.add(rootInfo);
+            }
+        }
+    }
+
+    // Create the dominator tree.
+    m_dominatorTree = computeDominatorTree(funcInst);
+
+    // Process the roots
+    for (const auto& rootInfo : rootInfos)
+    {
+        processRoot(rootInfo);
+    }
+}
+
+void LivenessContext::processModule()
+{
+    // When we process liveness, is prior to output for a target
+    // So post specialization
+
+    IRModuleInst* moduleInst = m_module->getModuleInst();
+
+    for (IRInst* child = moduleInst->getFirstDecorationOrChild(); child; child = child->getNextInst())
+    {
+        // We want to find all of the functions, and process them
+        if (auto funcInst = as<IRFunc>(child))
+        {
+            // Then we want to look through their definition
+            // inserting instructions that mark the liveness start/end
+            processFunction(funcInst);
+        }
+    }
+}
+
+} // anonymous
+
+void addLivenessTrackingToModule(IRModule* module)
+{
+    LivenessContext context(module);
+
+    context.processModule();
+}
+
+} // namespace Slang
+    
\ No newline at end of file
diff --git a/source/slang/slang-ir-liveness.h b/source/slang/slang-ir-liveness.h
new file mode 100644
index 000000000..39098ae04
--- /dev/null
+++ b/source/slang/slang-ir-liveness.h
@@ -0,0 +1,169 @@
+// slang-ir-liveness.h
+#ifndef SLANG_IR_LIVENESS_H
+#define SLANG_IR_LIVENESS_H
+
+namespace Slang
+{
+
+struct IRModule;
+
+/* 
+
+Liveness
+========
+
+## Status
+
+Currently liveness tracking only tracks local variables in functions. 
+
+In particular it doesn't handle:
+
+* PHI temporaries 
+* Variables that aren't constructed via IRVar
+* Variables that might be introduced via slang-ir-restructure-scoping.h/.cpp
+* Possible variable 'escape' via pointers (shouldn't be possible right now - but restructuring might introduce issues)
+* Any tracking around undefined values
+
+If enabled output source will output with SLANG_LIVE_START and SLANG_LIVE_END macros. It's a user space problem as to how to use these definitions (for example by adding a prelude).
+
+## Motivation
+
+At a first approximation liveness means variable is `in scope`. The underlying issue might be described as
+
+```HLSL
+struct SomeStruct
+{
+	int value;
+	int large[100];
+};
+
+int someFunction()
+{
+	int result = 0;
+
+	for (int i = 0; i < ...; ++i)
+	{
+		doSomething();
+
+		SomeStruct s;
+		s.value = ...;
+
+		doSomethingElse(s);
+
+		result += s.value;
+	}
+
+	return result;
+}
+```
+
+A compiler might hoist `s` outside of the loop, looking something more like...
+
+```
+int someFunction()
+{
+	SomeStruct s;
+	int result = 0;
+
+	for (int i = 0; i < ...; ++i)
+	{
+		doSomething();
+
+		s.value = ...;
+
+		result += doSomethingElse(s);
+	}
+
+	return result;
+}
+```
+
+The problem is that now `s` is in scope over the loop, and there is potential for values from one interation
+to be used in the next iteration. This isn't a problem in the original version because it is 'obvious' that
+a new `s` is constructed each iteration. The key observation being that when doSomething is executing, `s` doesn't exist,
+and so doesn't need to take any register space.
+
+Why hoist? Some compilers define variables via `alloca`s, and these allocas can only be placed at the start of the function. That being the case
+their scoping for where the contents is 'live' is lost.
+
+So liveness here is adding additional information about variables use. The start of the range is where there is a 'fresh' copy of the variable, and the 
+end is where where the values held in the variable can no longer alter execution results. 
+
+## Discussion
+
+The previous discussion of liveness could be described as being at the 'variable' level.
+
+Liveness could be tracked in a more fine grain manner - such as tracking field liveness. `s` has no `__init` and isn't 
+initialized in any way. s.value does set some state, but `large` is untouched. So in a sense s.value holds *all* of the 
+state of s at that point, and only s.value would need to be stored to reconstruct s (the rest could be undefined). 
+
+Is this more nuanced information useful to a downstream compilation? Maybe, but the downstream compiler could perform all the same 
+analysis. All it's really missing is knowing when there is a `fresh version` of s.
+
+How does this apply to undefined values?
+
+```
+int someFunction()
+{
+	int result = 0;
+	int v;				/// v's value is undefined
+
+	for (int i = 0; i < ...; ++i)
+	{
+		doSomething();
+
+		SomeStruct s;
+		s.value = v;
+
+		result += doSomethingElse(s);
+	}
+
+	return result;
+}
+```
+
+In this somewhat silly example, s.value is set to an undefined value. At one level you could say that s is *all* in an undefined state, 
+and therefore s is stateless. That's not quite right though because although v is undefined, it should probably be the same value 
+every loop. 
+
+Like before though, this may not matter too much in practice because a downstream compiler can see this behavior, and handle appropriately.
+
+Another way a compiler could `see` that it has a `fresh copy` within the loop, would be for all it's state to be set.
+
+```
+int someFunction()
+{
+	SomeStruct s;
+	
+	int result = 0;
+	
+	for (int i = 0; i < ...; ++i)
+	{
+		doSomething();
+
+		// (Note the syntax here is not Slang/HLSL, it's just meant to mean 'initialize s')
+		s = SomeStruct{};
+
+		s.value = v;
+
+		result += doSomethingElse(s);
+	}
+
+	return result;
+}
+```
+
+Here because of the initialization of *all* of `s`, a downstream compiler can infer that during `doSomething` it doesn't have to potentially store the contents
+of `s` because it will be wiped out after the function. 
+
+All of this gets more complex around branches. But again that is something a downstream compiler can track if it has a way of knowing when a variable is in scope. 
+Similarly calling into a function could return a struct that contains fields which aren't set - this is something a downstream compiler could determine when 
+fully specialized.
+*/
+
+	/// Adds LiveRangeStart and LiveRangeEnd instructions to demark the start and end of the liveness of a variable.
+void addLivenessTrackingToModule(IRModule* module);
+
+}
+
+#endif // SLANG_IR_LIVENESS_H
\ No newline at end of file
diff --git a/source/slang/slang-ir-restructure.h b/source/slang/slang-ir-restructure.h
index e08dba0d3..652429d2c 100644
--- a/source/slang/slang-ir-restructure.h
+++ b/source/slang/slang-ir-restructure.h
@@ -257,7 +257,7 @@ namespace Slang
     ///
     /// 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
+    /// In cases where our current restructuring approach is not powerful
     /// enough to handle something in the input CFG, diagnostic messages
     /// will be output to the given `sink`.
     ///
diff --git a/source/slang/slang-ir.cpp b/source/slang/slang-ir.cpp
index b53c247c3..782f259ee 100644
--- a/source/slang/slang-ir.cpp
+++ b/source/slang/slang-ir.cpp
@@ -2890,6 +2890,36 @@ namespace Slang
         return inst;
     }
 
+    IRLiveRangeStart* IRBuilder::emitLiveRangeStart(IRInst* referenced)
+    {
+        // This instruction doesn't produce any result, 
+        // so we make it's type void.
+        auto inst = createInst<IRLiveRangeStart>(
+            this,
+            kIROp_LiveRangeStart,
+            getVoidType(),
+            referenced);
+        
+        addInst(inst);
+
+        return inst;
+    }
+
+    IRLiveRangeEnd* IRBuilder::emitLiveRangeEnd(IRInst* referenced)
+    {
+        // This instruction doesn't produce any result, 
+        // so we make it's type void.
+        auto inst = createInst<IRLiveRangeEnd>(
+            this,
+            kIROp_LiveRangeEnd,
+            getVoidType(),
+            referenced);
+
+        addInst(inst);
+
+        return inst;
+    }
+
     IRInst* IRBuilder::emitExtractExistentialValue(
         IRType* type,
         IRInst* existentialValue)
diff --git a/source/slang/slang-options.cpp b/source/slang/slang-options.cpp
index c31006058..6705f836b 100644
--- a/source/slang/slang-options.cpp
+++ b/source/slang/slang-options.cpp
@@ -652,6 +652,7 @@ struct OptionsParser
             "  -save-stdlib <filename>: Save the StdLib modules to an archive file.\n"
             "  -save-stdlib-bin-source <filename>: Same as -save-stdlib but output\n"
             "      the data as a C array.\n"
+            "  -track-liveness: Enable liveness tracking. Places SLANG_LIVE_START, and SLANG_LIVE_END in output source to indicate value liveness.\n"
             "\n"
             "Deprecated options (allowed but ignored; may be removed in future):\n"
             "\n"
@@ -1000,6 +1001,10 @@ struct OptionsParser
                 {
                     requestImpl->disableDynamicDispatch = true;
                 }
+                else if (argValue == "-track-liveness")
+                {
+                    requestImpl->setTrackLiveness(true);
+                }
                 else if (argValue == "-verbose-paths")
                 {
                     requestImpl->getSink()->setFlag(DiagnosticSink::Flag::VerbosePath);
diff --git a/source/slang/slang.cpp b/source/slang/slang.cpp
index 985599022..3a180027a 100644
--- a/source/slang/slang.cpp
+++ b/source/slang/slang.cpp
@@ -4159,6 +4159,18 @@ void EndToEndCompileRequest::setDumpIntermediates(int enable)
     }
 }
 
+void EndToEndCompileRequest::setTrackLiveness(bool v)
+{
+    enableLivenessTracking = v;
+
+    // Change all existing targets to use the new setting.
+    auto linkage = getLinkage();
+    for (auto& target : linkage->targets)
+    {
+        target->setTrackLiveness(v);
+    }
+}
+
 void EndToEndCompileRequest::setDumpIntermediatePrefix(const char* prefix)
 {
     m_dumpIntermediatePrefix = prefix;