diff options
Diffstat (limited to 'source')
| -rw-r--r-- | source/slang/slang-compiler.cpp | 8 | ||||
| -rwxr-xr-x | source/slang/slang-compiler.h | 11 | ||||
| -rw-r--r-- | source/slang/slang-emit-c-like.cpp | 41 | ||||
| -rw-r--r-- | source/slang/slang-emit-c-like.h | 3 | ||||
| -rw-r--r-- | source/slang/slang-emit.cpp | 40 | ||||
| -rw-r--r-- | source/slang/slang-ir-dominators.h | 2 | ||||
| -rw-r--r-- | source/slang/slang-ir-inst-defs.h | 5 | ||||
| -rw-r--r-- | source/slang/slang-ir-insts.h | 43 | ||||
| -rw-r--r-- | source/slang/slang-ir-liveness.cpp | 533 | ||||
| -rw-r--r-- | source/slang/slang-ir-liveness.h | 169 | ||||
| -rw-r--r-- | source/slang/slang-ir-restructure.h | 2 | ||||
| -rw-r--r-- | source/slang/slang-ir.cpp | 30 | ||||
| -rw-r--r-- | source/slang/slang-options.cpp | 5 | ||||
| -rw-r--r-- | source/slang/slang.cpp | 12 |
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; |