diff options
Diffstat (limited to 'source')
| -rw-r--r-- | source/core/slang-array-view.h | 49 | ||||
| -rw-r--r-- | source/slang/slang-emit.cpp | 65 | ||||
| -rw-r--r-- | source/slang/slang-ir-eliminate-phis.cpp | 28 | ||||
| -rw-r--r-- | source/slang/slang-ir-eliminate-phis.h | 6 | ||||
| -rw-r--r-- | source/slang/slang-ir-liveness.cpp | 1034 | ||||
| -rw-r--r-- | source/slang/slang-ir-liveness.h | 25 | ||||
| -rw-r--r-- | source/slang/slang-ir.cpp | 4 |
7 files changed, 914 insertions, 297 deletions
diff --git a/source/core/slang-array-view.h b/source/core/slang-array-view.h index 6f5277f5f..f6ac92004 100644 --- a/source/core/slang-array-view.h +++ b/source/core/slang-array-view.h @@ -14,19 +14,19 @@ namespace Slang public: typedef ConstArrayView ThisType; - const T* begin() const { return m_buffer; } + SLANG_FORCE_INLINE const T* begin() const { return m_buffer; } - const T* end() const { return m_buffer + m_count; } + SLANG_FORCE_INLINE const T* end() const { return m_buffer + m_count; } - inline Index getCount() const { return m_count; } + SLANG_FORCE_INLINE Count getCount() const { return m_count; } - inline const T& operator [](Index idx) const + SLANG_FORCE_INLINE const T& operator [](Index idx) const { SLANG_ASSERT(idx >= 0 && idx < m_count); return m_buffer[idx]; } - inline const T* getBuffer() const { return m_buffer; } + SLANG_FORCE_INLINE const T* getBuffer() const { return m_buffer; } template<typename T2> Index indexOf(const T2& val) const @@ -78,7 +78,7 @@ namespace Slang { return true; } - const Index count = getCount(); + const Count count = getCount(); if (count != rhs.getCount()) { return false; @@ -96,27 +96,38 @@ namespace Slang } SLANG_FORCE_INLINE bool operator!=(const ThisType& rhs) const { return !(*this == rhs); } + ThisType head(Index index) const + { + SLANG_ASSERT(index >= 0 && index <= m_count); + return ThisType(m_buffer, index); + } + ThisType tail(Index index) const + { + SLANG_ASSERT(index >= 0 && index <= m_count); + return ThisType(m_buffer + index, m_count - index); + } + ConstArrayView() : m_buffer(nullptr), m_count(0) { } - ConstArrayView(const T* buffer, Index count) : + ConstArrayView(const T* buffer, Count count) : m_buffer(const_cast<T*>(buffer)), m_count(count) { } protected: - ConstArrayView(T* buffer, Index count) : + ConstArrayView(T* buffer, Count count) : m_buffer(buffer), m_count(count) { } T* m_buffer; ///< Note that this isn't const, as is used for derived class ArrayView also - Index m_count; + Count m_count; }; template<typename T> @@ -126,7 +137,7 @@ namespace Slang } template<typename T> - ConstArrayView<T> makeConstArrayView(const T* buffer, Index count) + ConstArrayView<T> makeConstArrayView(const T* buffer, Count count) { return ConstArrayView<T>(buffer, count); } @@ -157,6 +168,9 @@ namespace Slang using Super::end; T* end() { return m_buffer + m_count; } + using Super::head; + using Super::tail; + using Super::operator[]; inline T& operator [](Index idx) { @@ -167,6 +181,17 @@ namespace Slang using Super::getBuffer; inline T* getBuffer() { return m_buffer; } + ThisType head(Index index) + { + SLANG_ASSERT(index >= 0 && index <= m_count); + return ThisType(m_buffer, index); + } + ThisType tail(Index index) + { + SLANG_ASSERT(index >= 0 && index <= m_count); + return ThisType(m_buffer + index, m_count - index); + } + ArrayView() : Super() {} ArrayView(T* buffer, Index size) :Super(buffer, size) {} }; @@ -178,7 +203,7 @@ namespace Slang } template<typename T> - ArrayView<T> makeArrayView(T* buffer, Index count) + ArrayView<T> makeArrayView(T* buffer, Count count) { return ArrayView<T>(buffer, count); } @@ -186,7 +211,7 @@ namespace Slang template<typename T, size_t N> ArrayView<T> makeArrayView(T (&arr)[N]) { - return ArrayView<T>(arr, Index(N)); + return ArrayView<T>(arr, Count(N)); } diff --git a/source/slang/slang-emit.cpp b/source/slang/slang-emit.cpp index dd176d859..baf0949bb 100644 --- a/source/slang/slang-emit.cpp +++ b/source/slang/slang-emit.cpp @@ -734,33 +734,54 @@ Result linkAndOptimizeIR( lowerBitCast(targetRequest, irModule); simplifyIR(irModule); - // - // Downstream targets may benefit from having live-range information for - // local variables, and our IR currently encodes a reasonably good version - // of that information. At this point we will insert live-range markers - // for local variables, on when such markers are requested. - // - // After this point in optimization, any passes that introduce new - // temporary variables into the IR module should take responsibility for - // producing their own live-range information. - // - if (codeGenContext->shouldTrackLiveness()) { - addLivenessTrackingToModule(irModule); + // Storage for liveness information + List<LivenessLocation> livenessLocations; + const bool shouldTrackLiveness = codeGenContext->shouldTrackLiveness(); - dumpIRIfEnabled(codeGenContext, irModule, "LIVENESS"); - } + // + // Downstream targets may benefit from having live-range information for + // local variables, and our IR currently encodes a reasonably good version + // of that information. At this point we will insert live-range markers + // for local variables, on when such markers are requested. + // + // After this point in optimization, any passes that introduce new + // temporary variables into the IR module should take responsibility for + // producing their own live-range information. + // + if (shouldTrackLiveness) + { + LivenessUtil::locateVariables(irModule, livenessLocations); + } + + // As a late step, we need to take the SSA-form IR and move things *out* + // of SSA form, by eliminating all "phi nodes" (block parameters) and + // introducing explicit temporaries instead. Doing this at the IR level + // means that subsequent emit logic doesn't need to contend with the + // complexities of blocks with parameters. + // + + { + // We only want to accumulate locations if liveness tracking is enabled. + List<LivenessLocation>* locsPtr = shouldTrackLiveness ? &livenessLocations : nullptr; + + eliminatePhis(codeGenContext, locsPtr, irModule); +#if 0 + dumpIRIfEnabled(codeGenContext, irModule, "PHIS ELIMINATED"); +#endif + } + + // If liveness is enabled add liveness ranges based on the accumulated liveness locations + + if (shouldTrackLiveness) + { + LivenessUtil::addLivenessRanges(irModule, livenessLocations); - // As a late step, we need to take the SSA-form IR and move things *out* - // of SSA form, by eliminating all "phi nodes" (block parameters) and - // introducing explicit temporaries instead. Doing this at the IR level - // means that subsequent emit logic doesn't need to contend with the - // complexities of blocks with parameters. - // - eliminatePhis(codeGenContext, irModule); #if 0 - dumpIRIfEnabled(codeGenContext, irModule, "PHIS ELIMINATED"); + dumpIRIfEnabled(codeGenContext, irModule, "LIVENESS"); #endif + } + } // TODO: We need to insert the logic that fixes variable scoping issues // here (rather than doing it very late in the emit process), because diff --git a/source/slang/slang-ir-eliminate-phis.cpp b/source/slang/slang-ir-eliminate-phis.cpp index 2891376eb..ab26bb8eb 100644 --- a/source/slang/slang-ir-eliminate-phis.cpp +++ b/source/slang/slang-ir-eliminate-phis.cpp @@ -68,12 +68,14 @@ struct PhiEliminationContext IRModule* m_module = nullptr; SharedIRBuilder m_sharedBuilder; IRBuilder m_builder; + List<LivenessLocation>* m_livenessLocations; - PhiEliminationContext(CodeGenContext* codeGenContext, IRModule* module) + PhiEliminationContext(CodeGenContext* codeGenContext, List<LivenessLocation>* ioLivenessLocations, IRModule* module) : m_codeGenContext(codeGenContext) , m_module(module) , m_sharedBuilder(module) , m_builder(m_sharedBuilder) + , m_livenessLocations(ioLivenessLocations) {} // We start with the top-down logic of the pass, which is to process @@ -795,7 +797,25 @@ struct PhiEliminationContext // auto& dstParam = assignment.param; auto& srcArg = assignment.arg; - m_builder.emitStore(dstParam.temp, *srcArg.currentValPtr); + auto storeInst = m_builder.emitStore(dstParam.temp, *srcArg.currentValPtr); + + // If we have liveness tracking add the location + if (m_livenessLocations) + { + LivenessLocation location; + location.root = dstParam.temp; + + // A store could (perhaps?) consist of multiple instructions + // If we make liveness *after* the store, then it implies anything stored + // into the location might be lost. + // + // Therefore is seems appropriate to say the variable is *live* *before* the store instruction. + location.startLocation = IRInsertLoc::before(storeInst); + location.function = m_func; + + m_livenessLocations->add(location); + } + // // Once the store is emitted, the assignment has been performed, // and it can move to the _done_ state. @@ -885,9 +905,9 @@ struct PhiEliminationContext } }; -void eliminatePhis(CodeGenContext* codeGenContext, IRModule* module) +void eliminatePhis(CodeGenContext* codeGenContext, List<LivenessLocation>* ioLocations, IRModule* module) { - PhiEliminationContext context(codeGenContext, module); + PhiEliminationContext context(codeGenContext, ioLocations, module); context.eliminatePhisInModule(); } diff --git a/source/slang/slang-ir-eliminate-phis.h b/source/slang/slang-ir-eliminate-phis.h index 58690c012..90eb485e1 100644 --- a/source/slang/slang-ir-eliminate-phis.h +++ b/source/slang/slang-ir-eliminate-phis.h @@ -1,6 +1,8 @@ // slang-ir-eliminate-phis.h #pragma once +#include "slang-ir-liveness.h" + namespace Slang { struct CodeGenContext; @@ -12,5 +14,7 @@ namespace Slang /// so that it is more suitable for emission on targets that /// are not themselves based on an SSA representation. /// - void eliminatePhis(CodeGenContext* context, IRModule* module); + /// ioLocations is optional - pass nullptr if not required. + /// If set, will have liveness location information appended to the list + void eliminatePhis(CodeGenContext* context, List<LivenessLocation>* ioLocations, IRModule* module); } diff --git a/source/slang/slang-ir-liveness.cpp b/source/slang/slang-ir-liveness.cpp index 414f18d77..1e88763fd 100644 --- a/source/slang/slang-ir-liveness.cpp +++ b/source/slang/slang-ir-liveness.cpp @@ -8,14 +8,10 @@ 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'. @@ -83,41 +79,58 @@ is created that is then just copied into the variable. That temporary being some could perhaps have liveness issues. */ -/* This implementation could potentially be improved in a few ways: - -## Use Dominator tree block indexing +namespace { // anonymous -The dominator tree has a mapping from block insts to integer values. These integer value could be used to allow information about blocks to -be stored in an array. A downside, would be exposing that aspect of the implementation to the dominator tree. +/* +A helper class to enable using a backing array, used in a stack like manner. */ +template <typename T> +class RAIIStackArray +{ +public: + ArrayView<T> getView() { return makeArrayView(m_list->getBuffer() + m_startIndex, m_list->getCount() - m_startIndex); } + ConstArrayView<T> getConstView() const { return makeConstArrayView(m_list->getBuffer() + m_startIndex, m_list->getCount() - m_startIndex); } -## Store if a block has an access instruction + void setCount(Count count) { m_list->setCount(m_startIndex + count); } + Count getCount() const { return m_list->getCount() - m_startIndex; } -As it stands, when traversing the tree to find the last access, the implementation searches for each block backwards to find the last access -by looking if it's in the m_accessSet. + T& operator[](Index i) { return (*m_list)[m_startIndex + i]; } + const T& operator[](Index i) const { return (*m_list)[m_startIndex + i]; } -This searching could be avoided, by when accesses are added the block they are in is marked as having an access. If a block had no accesses -this would remove the linear search for the first access instruction, if the block indicates it doesn't have any. The downside being that every -access would also have to mark the block it is in. -*/ + RAIIStackArray(List<T>* list): + m_startIndex(list->getCount()), + m_list(list) + { + } + ~RAIIStackArray() + { + m_list->setCount(m_startIndex); + } -namespace { // anonymous + const Index m_startIndex; + List<T>*const m_list; +}; 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 + typedef LivenessLocation Location; + + enum class BlockIndex : Index; + + // NOTE! Care must be taken changing the order. + // canPromote checks if a result can be 'promoted'. + enum class BlockResult { Found, ///< All paths were either not dominated, found NotFound, ///< It is dominated but no access was found. Visited, ///< The block has been visited (as part of a traversal), but does not yet have a result. Used to detect loops. + NotVisited, ///< Not visited NotDominated, ///< If it's not dominated it can't have a liveness end CountOf, }; /// True if a result can be premoted `from` to `to` - static bool canPromote(FoundResult from, FoundResult to) { return Index(to) <= Index(from) && from != FoundResult::NotDominated; } + static bool canPromote(BlockResult from, BlockResult to) { return (from == BlockResult::NotVisited) || (Index(to) <= Index(from) && from != BlockResult::NotDominated); } enum class AccessType { @@ -125,25 +138,48 @@ struct LivenessContext Alias, ///< Produces an alias to the root Access, ///< Is an access to the root (perhaps through an alias) }; - - struct RootInfo + + /// Block info (indexed via BlockIndex), that is valid across analysing liveness of a root + struct BlockInfo { - IRInst* root; - IRLiveRangeStart* liveStart; - }; - - /// Processor a successor to a block - FoundResult processSuccessor(IRBlock* block); + void reset() + { + result = BlockResult::NotVisited; + runStart = 0; + runCount = 0; + lastInst = nullptr; + instCount = 0; + } + void resetResult() + { + result = BlockResult::NotVisited; + } - /// Process a block - FoundResult processBlock(IRBlock* block); + BlockResult result; ///< The result for this block + Index runStart; ///< The start index in m_instRuns index. This defines a instruction of interest in order in a block. + Count runCount; ///< The count of the amount insts in the run + IRInst* lastInst; ///< Last inst seen + Count instCount; ///< The total amount of start/access instruction seen in the block + }; - /// Process a 'root'. A variable that has liveness tracking - void processRoot(const RootInfo& rootInfo); + /// Block info (indexed via BlockIndex), that is valid across a function + struct FunctionBlockInfo + { + void init(IRBlock* inBlock) + { + block = inBlock; + successorsStart = 0; + successorsCount = 0; + } - /// Process the module - void processModule(); + IRBlock* block; + Index successorsStart; ///< Indexes into block successors + Count successorsCount; + }; + /// Process all the locations + void processLocations(const List<Location>& locations); + LivenessContext(IRModule* module): m_module(module) { @@ -151,144 +187,358 @@ struct LivenessContext m_builder.init(m_sharedBuilder); } - /// Process a function in the module - void _processFunction(IRFunc* funcInst); + /// For a given live range start find it's end/s and insert a LiveRangeEnd/s + /// Can only be called after a call to _findAliasesAndAccesses for the root. + void _findAndEmitRangeEnd(IRLiveRangeStart* liveStart); + + /// Process a successor to a block + /// Can only be called after a call to _findAliasesAndAccesses for the root. + BlockResult _processSuccessor(BlockIndex blockIndex); - // Add a live end instruction at the start of block, referencing the root 'root'. - void _addLiveRangeEndAtBlockStart(IRBlock* block, IRInst* root); + /// Process a block + /// Can only be called after a call to _findAliasesAndAccesses for the root. + BlockResult _processBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run); + + /// Process all the locations in the function + /// NOTE: All locations must be to the same function, and ordered by root. + void _processLocationsInFunction(const Location* start, Count count); + + /// Process a root + /// NOTE: All locations must be to the same root + void _processRoot(const Location* locations, Count count); - /// 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); + /// Find all the aliases and accesses to the root + /// The information is stored in m_accessSet and m_aliases + void _findAliasesAndAccesses(IRInst* root); /// Add a result for the block - /// Allows for promotion from NotFound -> Found if there is already a result - FoundResult _addResult(IRBlock* block, FoundResult result); + /// Allows for promotion if there is already a result + BlockResult _addBlockResult(BlockIndex blockIndex, BlockResult result); + + /// Find the runs of 'important instructions' all of the blocks + /// 'important instructions are root starts, and accesses to the root + /// The run stores these instructions in the order they appear in the block within the run. + void _findInstRunsForBlocks(); + + /// Adds an instruction that is an access to the root + void _addAccessInst(IRInst* inst); + /// Add a live range start + void _addStartInst(IRLiveRangeStart* inst) { _addInst(inst); } + /// Add an 'important instruction' that is significant for liveness tracking and so will be added to run + void _addInst(IRInst* inst); + + /// True if it's an instruction of interest and so will go within a run for a block + bool _isRunInst(IRInst* inst); + + // Returns the index in the run of a start for the current root, else -1 + Index _indexOfRootStart(const ConstArrayView<IRInst*>& run); + + /// Returns the last index within the run which is an access, else -1 + Index _findLastAccess(const ConstArrayView<IRInst*>& run); + + /// Adds an LiveRangeEnd for the root after `inst` if there isn't one there already + void _maybeAddEndAfterInst(IRInst* inst); + + void _maybeAddEndBeforeInst(IRInst* inst); - RefPtr<IRDominatorTree> m_dominatorTree; ///< The dominator tree for the current function + // Add a live end instruction at the start of block, referencing the root + void _maybeAddEndAtBlockStart(IRBlock* block); - RootInfo m_rootInfo; ///< The root item we are searching for accesses to, to determine scope/liveness - IRBlock* m_rootBlock; ///< The block the root is in + /// Look from inst for an LiveEndRange to the root. + IRInst* _findRootEnd(IRInst* inst); + + /// Complete the block using the run, which can *cannot* contain the current root start + BlockResult _completeBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run); + + /// Get block info + BlockInfo* _getBlockInfo(BlockIndex blockIndex) { return &m_blockInfos[Index(blockIndex)]; } + + /// Get the block from the index + IRBlock* _getBlock(BlockIndex blockIndex) const { return m_functionBlockInfos[Index(blockIndex)].block; } + + /// Gets the instructions of interest for this info, in the order they appear within the block + ConstArrayView<IRInst*> _getRun(const BlockInfo* info) + { + IRInst*const* buffer = m_instRuns.getBuffer(); + return ConstArrayView<IRInst*>(buffer + info->runStart, info->runCount); + } + /// Gets all of the successors for the blockIdnex + ConstArrayView<BlockIndex> _getSuccessors(BlockIndex blockIndex) + { + const auto& info = m_functionBlockInfos[Index(blockIndex)]; + return makeConstArrayView(m_blockSuccessors.getBuffer() + info.successorsStart, info.successorsCount); + } + + RefPtr<IRDominatorTree> m_dominatorTree; ///< The dominator tree for the current function + + IRLiveRangeStart* m_rootLiveStart = nullptr; ///< The current live start for the root + IRBlock* m_rootLiveStartBlock = nullptr; ///< The current block for the live start + + IRInst* m_root = nullptr; ///< The current root + IRBlock* m_rootBlock = nullptr; ///< 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<BlockResult> m_successorResults; ///< Storage for successor results - List<IRInst*> m_aliases; ///< A list of instructions that alias to 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 + HashSet<IRInst*> m_accessSet; ///< If instruction is in set it is an `access` indicating it must be live at least up to this instruction + + Dictionary<IRBlock*, BlockIndex> m_blockIndexMap; ///< Map from a block to a block index + List<BlockInfo> m_blockInfos; ///< Information about blocks, for the current root + List<FunctionBlockInfo> m_functionBlockInfos; ///< Information about blocks across the current function + List<BlockIndex> m_blockSuccessors; ///< Successors for a blocks, accessed via + + List<IRInst*> m_instRuns; ///< Instructions of interest in order. Indexed into via BlockInfo [runStart, runStart + runCount) + + List<IRLiveRangeStart*> m_liveRangeStarts; ///< Live range starts for a root IRModule* m_module; SharedIRBuilder m_sharedBuilder; IRBuilder m_builder; }; -void LivenessContext::_addLiveRangeEndAtBlockStart(IRBlock* block, IRInst* root) +void LivenessContext::_maybeAddEndAtBlockStart(IRBlock* block) { // Insert before the first ordinary inst auto inst = block->getFirstOrdinaryInst(); + // A block has to end with a terminator... so must always be an ordinary inst, if there is a function body SLANG_ASSERT(inst); + _maybeAddEndBeforeInst(inst); +} - m_builder.setInsertLoc(IRInsertLoc::before(inst)); - - // Add the live end inst - m_builder.emitLiveRangeEnd(root); +LivenessContext::BlockResult LivenessContext::_addBlockResult(BlockIndex blockIndex, BlockResult result) +{ + auto& currentResult = _getBlockInfo(blockIndex)->result; + // Check we can promote + SLANG_ASSERT(canPromote(currentResult, result)); + currentResult = result; + return result; } -IRInst* LivenessContext::_findLastAccessInBlock(IRBlock* block) +LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex blockIndex) { - // If we are in the root block, we don't want to search *before* the liveStart - IRInst* lastInst = (block == m_rootBlock) ? m_rootInfo.liveStart : nullptr; + auto blockInfo = _getBlockInfo(blockIndex); + + // Check if there is already a result for this block. + // If there is just return that. + auto result = blockInfo->result; - // Search backwards for first access - for (IRInst* cur = block->getLastChild(); cur != lastInst; cur = cur->getPrevInst()) + switch (result) { - SLANG_ASSERT(cur); + case BlockResult::NotVisited: + { + // If not visited we need to process + break; + } + case BlockResult::Visited: + { + const auto block = _getBlock(blockIndex); + + // If visited, it can't have a domination issue + // Unless it is the start block (the block containing live start) *and* the root is + // in the block. + // The live start can only be after the var, because the var is only in scope then. + // + + // We need to check if we are in the live start block, as we then need to process + // up until the live start. + if (block == m_rootLiveStartBlock) + { + // We want the run to search to go from the start up to *this specific* liveness start + // (as opposed to any liveness start for the root) + auto run = _getRun(blockInfo); + + // We need to fix the run to be *after* this specific start + const Index startIndex = run.indexOf(m_rootLiveStart); + SLANG_ASSERT(startIndex >= 0); - if (m_accessSet.Contains(cur)) + // We want to run all the way up to the start + return _processBlock(blockIndex, run.head(startIndex)); + } + + // Otherwise just return result + return result; + } + default: { - return cur; + // Otherwise just return result + return result; } } - return nullptr; + const auto block = _getBlock(blockIndex); + + // 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 _addBlockResult(blockIndex, BlockResult::NotDominated); + } + + // Mark that it is visited + _addBlockResult(blockIndex, BlockResult::Visited); + + // Else process the block to try and find the last used instruction + return _processBlock(blockIndex, _getRun(blockInfo)); } -LivenessContext::FoundResult LivenessContext::_addResult(IRBlock* block, FoundResult result) +Index LivenessContext::_indexOfRootStart(const ConstArrayView<IRInst*>& run) { - auto currentResultPtr = m_blockResult.TryGetValueOrAdd(block, result); - if (currentResultPtr) + const Count count = run.getCount(); + for (Index i = 0; i < count; ++i) { - const auto currentResult = *currentResultPtr; - - // Check we can promote - SLANG_ASSERT(canPromote(currentResult, result)); + if (auto liveStart = as<IRLiveRangeStart>(run[i])) + { + if (liveStart->getReferenced() == m_root) + { + return i; + } + } + } + return -1; +} - // Set the new result - *currentResultPtr = result; +Index LivenessContext::_findLastAccess(const ConstArrayView<IRInst*>& run) +{ + for (Index i = run.getCount() - 1; i >= 0; --i) + { + // If it's not a live start, it must be an access + if (as<IRLiveRangeStart>(run[i]) == nullptr) + { + // Check it really is an access inst.. + SLANG_ASSERT(_isRunInst(run[i])); + return i; + } } + return -1; +} - return result; +IRInst* LivenessContext::_findRootEnd(IRInst* inst) +{ + for (auto cur = inst; cur; cur = cur->getNextInst()) + { + IRLiveRangeEnd* end = as<IRLiveRangeEnd>(cur); + if (end == nullptr) + { + break; + } + + // If we hit an end which is already the root, then we don't need to add an + // end of the root + if (end->getReferenced() == m_root) + { + return cur; + } + } + + return nullptr; } -LivenessContext::FoundResult LivenessContext::processSuccessor(IRBlock* block) +void LivenessContext::_maybeAddEndAfterInst(IRInst* inst) { - // Check if there is already a result for this block. - // If there is just return that. - auto res = m_blockResult.TryGetValue(block); - if (res) + if (!_findRootEnd(inst->getNextInst())) { - return *res; + // Just add end of scope after the inst + m_builder.setInsertLoc(IRInsertLoc::after(inst)); + // Add the live end inst + m_builder.emitLiveRangeEnd(m_root); } +} - // 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)) +void LivenessContext::_maybeAddEndBeforeInst(IRInst* inst) +{ + if (!_findRootEnd(inst)) { - return _addResult(block, FoundResult::NotDominated); + // Just add end of scope after the inst + m_builder.setInsertLoc(IRInsertLoc::before(inst)); + // Add the live end inst + m_builder.emitLiveRangeEnd(m_root); } +} - // Mark that it is visited - m_blockResult.Add(block, FoundResult::Visited); +LivenessContext::BlockResult LivenessContext::_completeBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run) +{ + // We can't have a root start in the run! + SLANG_ASSERT(_indexOfRootStart(run) < 0); - // Else process the block to try and find the last used instruction - return processBlock(block); + // Look for the last access + const auto lastAccessIndex = _findLastAccess(run); + + // If we found one, that is the end of the range + if (lastAccessIndex >= 0) + { + IRInst* lastAccessInst = run[lastAccessIndex]; + + // Insert an end after the last access (if not one already) + _maybeAddEndAfterInst(lastAccessInst); + + // Add the result + return _addBlockResult(blockIndex, BlockResult::Found); + } + + // We didn't find anything, so mark as not found + return _addBlockResult(blockIndex, BlockResult::NotFound); } -LivenessContext::FoundResult LivenessContext::processBlock(IRBlock* block) +LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run) { - // Find all the successors for this block - auto successors = block->getSuccessors(); - const Index count = successors.getCount(); + // Note that the run must be some part of the run for the block indicated by blockIndex. One of + // + // * If root start block - before the start (if accessed via successor) + // * If root start block - after the start (if accessed initially in search) + // * Otherwise the whole run for the block + // + // Since this is the case, we know start is not part of the run + SLANG_ASSERT(run.indexOf(m_rootLiveStart) < 0); - // We need to store of the results for successors - List<FoundResult> successorResults; - successorResults.setCount(count); + // If there is *another* start to the same root, we can't traverse to other blocks, and the last access + // in this block must be the result + { + // NOTE! We shouldn't/can't use run.indexOf here, because we are looking for *any* start to the root + // _indexOfRootStart does this search. + // Moreover we know (it's a condition on run passed into this function) run cannot contain the root start. + const Index startIndex = _indexOfRootStart(run); + if (startIndex >= 0) + { + // Complete the block with this run + return _completeBlock(blockIndex, run.head(startIndex)); + } + } // Zero initialize all the counts - Index foundCounts[Index(FoundResult::CountOf)] = { 0 }; + Index foundCounts[Index(BlockResult::CountOf)] = { 0 }; + // Find all the successors for this block + auto successors = _getSuccessors(blockIndex); + + const Index successorCount = successors.getCount(); + + // Set up space to store successor results + RAIIStackArray<BlockResult> successorResults(&m_successorResults); + successorResults.setCount(successorCount); + + for (Index i = 0; i < successorCount; ++i) { - auto cur = successors.begin(); - for (Index i = 0; i < count; ++i, ++cur) - { - auto succ = *cur; + const auto successorBlockIndex = successors[i]; - // Process the successor - const auto successorResult = processSuccessor(succ); + // NOTE! Care is needed around successorResults, because _processorSuccessor may cause the underlying list + // to be reallocated. + // If we always access through successorResults (ie RAIIStackArray type), things will be fine though. + + // Process the successor + const auto successorResult = _processSuccessor(successorBlockIndex); - // Store the result - successorResults[i] = successorResult; + successorResults[i] = successorResult; - // Change counts depending on the result - foundCounts[Index(successorResult)]++; - } + // Change counts depending on the result + foundCounts[Index(successorResult)]++; } - const Index foundCount = foundCounts[Index(FoundResult::Found)]; - const Index notFoundCount = foundCounts[Index(FoundResult::NotFound)]; + const Index foundCount = foundCounts[Index(BlockResult::Found)]; + const Index notFoundCount = foundCounts[Index(BlockResult::NotFound)]; - const Index otherCount = count - (foundCount + notFoundCount); + const Index otherCount = successorCount - (foundCount + notFoundCount); // 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 @@ -296,65 +546,71 @@ LivenessContext::FoundResult LivenessContext::processBlock(IRBlock* block) if (foundCount > 0) { // If all successors have result, or are not dominated - if (foundCount + otherCount == count) + if (foundCount + otherCount == successorCount) { - return _addResult(block, FoundResult::Found); + return _addBlockResult(blockIndex, BlockResult::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 successorResultsView = successorResults.getConstView(); + + for (Index i = 0; i < successorCount; ++i) { - auto successor = *cur; - const auto successorResult = successorResults[i]; - if (successorResult == FoundResult::NotFound) + const auto successorResult = successorResultsView[i]; + + if (successorResult == BlockResult::NotFound) { - _addLiveRangeEndAtBlockStart(successor, m_rootInfo.root); - _addResult(successor, FoundResult::Found); + const auto successorBlockIndex = successors[i]; + _maybeAddEndAtBlockStart(_getBlock(successorBlockIndex)); + _addBlockResult(successorBlockIndex, BlockResult::Found); } } // This block, can now be marked as found - return _addResult(block, FoundResult::Found); + return _addBlockResult(blockIndex, BlockResult::Found); } - // Search the instructions in this block in reverse order, to find last access - IRInst* lastAccess = _findLastAccessInBlock(block); - - // Wasn't an access so we are done - if (lastAccess == nullptr) - { - return _addResult(block, FoundResult::NotFound); - } + return _completeBlock(blockIndex, run); +} + +void LivenessContext::_addInst(IRInst* inst) +{ + // Get the block it's in + auto block = as<IRBlock>(inst->getParent()); + + // Get the index to get the info + auto blockIndex = m_blockIndexMap[block]; - // Can never be a terminator, because logic to find the access instructions does not - // include terminators. - SLANG_ASSERT(as<IRTerminatorInst>(lastAccess) == nullptr); + auto blockInfo = _getBlockInfo(blockIndex); - // Just add end of scope after the inst - m_builder.setInsertLoc(IRInsertLoc::after(lastAccess)); + // Increase the count + ++blockInfo->instCount; - // Add the live end inst - m_builder.emitLiveRangeEnd(m_rootInfo.root); - return _addResult(block, FoundResult::Found); + // Record that this is an instruction of interest for this block + // + // This only really exists to capture the scenario of only having one inst in a block, so we can just overwrite what's + // already there. + blockInfo->lastInst = inst; } -void LivenessContext::processRoot(const RootInfo& rootInfo) +void LivenessContext::_addAccessInst(IRInst* inst) { - // Clear the work structures - m_accessSet.Clear(); - m_aliases.clear(); - m_blockResult.Clear(); + // Add to the access set + m_accessSet.Add(inst); - auto root = rootInfo.root; + // Add the instruction to the block info + _addInst(inst); +} + +void LivenessContext::_findAliasesAndAccesses(IRInst* root) +{ + // Clear all the aliases + m_aliases.clear(); + // Clear the access set + m_accessSet.Clear(); - // Store root information, so don't have to pass around methods - m_rootInfo = rootInfo; - m_rootBlock = as<IRBlock>(root->parent); - // 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, @@ -391,87 +647,110 @@ void LivenessContext::processRoot(const RootInfo& rootInfo) // 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 kIROp_getElementPtr: { - case AccessType::Alias: + base = static_cast<IRGetElementPtr*>(cur)->getBase(); + accessType = AccessType::Alias; + break; + } + case kIROp_FieldAddress: { - // Add this instruction to the aliases - m_aliases.add(cur); + base = static_cast<IRFieldAddress*>(cur)->getBase(); + accessType = AccessType::Alias; break; } - case AccessType::Access: + case kIROp_getAddr: { - m_accessSet.Add(cur); + 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: + { + _addAccessInst(cur); + break; + } + default: break; } } } } +} + +void LivenessContext::_findAndEmitRangeEnd(IRLiveRangeStart* liveRangeStart) +{ + // Reset the result + for (auto& blockInfo : m_blockInfos) + { + blockInfo.resetResult(); + } + + // Store root information, so don't have to pass around methods + m_rootLiveStart = liveRangeStart; + m_rootLiveStartBlock = as<IRBlock>(liveRangeStart->getParent()); + + m_root = liveRangeStart->getReferenced(); + m_rootBlock = as<IRBlock>(m_root->parent); + + // If either of these asserts fail it probably means there hasn't been a call + // to `_findAliasesAndAccesses` which is required before this function can be called. + // + // There must be at least one alias (the root itself!) + SLANG_ASSERT(m_aliases.getCount() > 0); + // The first alias should be the root itself + SLANG_ASSERT(m_aliases[0] == m_root); // Now we want to find the last access in the graph of successors // @@ -488,23 +767,288 @@ void LivenessContext::processRoot(const RootInfo& rootInfo) // detect a loop. In most respect Visited behaves in the same manner as NotDominated. { + const BlockIndex rootStartBlockIndex = m_blockIndexMap[m_rootLiveStartBlock]; + auto blockInfo = _getBlockInfo(rootStartBlockIndex); + auto run = _getRun(blockInfo); + + // The run *must* contain this specific start start + const auto startIndex = run.indexOf(m_rootLiveStart); + SLANG_ASSERT(startIndex >= 0); + + // Make run scanning start *after* the start + run = run.tail(startIndex + 1); + // Mark the root as visited to stop an infinite loop - _addResult(m_rootBlock, FoundResult::Visited); + _addBlockResult(rootStartBlockIndex, BlockResult::Visited); // Recursively find results - auto foundResult = processBlock(m_rootBlock); + auto foundResult = _processBlock(rootStartBlockIndex, run); - if (foundResult == FoundResult::NotFound) + if (foundResult == BlockResult::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); + _maybeAddEndAfterInst(m_rootLiveStart); } } + + // Set back to nullptr for safety + m_rootLiveStart = nullptr; + m_root = nullptr; + m_rootBlock = nullptr; + m_rootLiveStartBlock = nullptr; } -void LivenessContext::_processFunction(IRFunc* funcInst) +bool LivenessContext::_isRunInst(IRInst* inst) +{ + const auto op = inst->getOp(); + + // If it's a live start then we need to track + if (op == kIROp_LiveRangeStart) + { + return true; + } + + // NOTE! + // These are the only ops *currently* that indicate an access. + // Has to be consistent with `_findAliasesAndAccesses` + if (op == kIROp_Call || + op == kIROp_Load || + op == kIROp_Call) + { + // Just because it's the right type *doesn't* mean it's an access, it has to also + // be in the access set + return m_accessSet.Contains(inst); + } + + return false; +} + +void LivenessContext::_findInstRunsForBlocks() +{ + const Count count = m_blockInfos.getCount(); + for (Index i = 0; i < count; ++i) + { + auto& blockInfo = m_blockInfos[i]; + + if (blockInfo.instCount == 0) + { + // Nothing to do if it's empty + SLANG_ASSERT(blockInfo.runCount == 0); + } + else if (blockInfo.instCount == 1) + { + // This is the easy case, since we don't need to determine the order of the instructions + blockInfo.runStart = m_instRuns.getCount(); + blockInfo.runCount = 1; + SLANG_ASSERT(blockInfo.lastInst); + m_instRuns.add(blockInfo.lastInst); + continue; + } + else + { + // TODO(JS): + // NOTE That we don't need to keep all accesses in the run, only the last accesses + // prior to a start or end of the block. + // + // For now we just add them all. + + const auto start = m_instRuns.getCount(); + blockInfo.runStart = start; + blockInfo.runCount = blockInfo.instCount; + + m_instRuns.setCount(start + blockInfo.instCount); + IRInst** dst = m_instRuns.getBuffer() + start; + + // Find all of the instructions of interest in order + auto block = _getBlock(BlockIndex(i)); + + for (auto inst : block->getChildren()) + { + if (_isRunInst(inst)) + { + *dst++ = inst; + if (dst == m_instRuns.end()) + { + break; + } + } + } + SLANG_ASSERT(dst == m_instRuns.end()); + } + + // The run count and the inst count must match at this point + SLANG_ASSERT(blockInfo.runCount == blockInfo.instCount); + } +} + +void LivenessContext::_processRoot(const Location* locations, Count locationsCount) +{ + if (locationsCount <= 0) + { + return; + } + + // Reset the order range for all blocks + for (auto& info : m_blockInfos) + { + info.reset(); + } + m_instRuns.clear(); + + auto root = locations[0].root; + + // Add all the live starts + m_liveRangeStarts.setCount(locationsCount); + for (Index i = 0; i < locationsCount; ++i) + { + const auto& location = locations[i]; + SLANG_ASSERT(location.root == root); + + // Add the start location + m_builder.setInsertLoc(location.startLocation); + // Emit the range start + auto liveStart = m_builder.emitLiveRangeStart(location.root); + + // Save the start + m_liveRangeStarts[i] = liveStart; + + _addStartInst(liveStart); + } + + // Find all of the aliases and access to this root + _findAliasesAndAccesses(root); + + // Find the runs of 'instructions of interest' (accesses/starts) for all the blocks + _findInstRunsForBlocks(); + + // Now we want to find all of the ends for each start + for (auto liveStart : m_liveRangeStarts) + { + // We want to process this RangeStart for the root, to find all of the ends + _findAndEmitRangeEnd(liveStart); + } +} + +void LivenessContext::_processLocationsInFunction(const Location* locations, Count count) +{ + if (count <= 0) + { + return; + } + + const auto func = locations[0].function; + SLANG_UNUSED(func); + + // Create the dominator tree, for the function + m_dominatorTree = computeDominatorTree(func); + + // We are going to precalculate a variety of things for blocks. + // Most processing is performed via BlockIndex, so we need to set up a map from the block pointer to the index + // By having as an index we can easily/quickly associate information with blocks with arrays + + // Set up the map from blocks to indices + m_blockIndexMap.Clear(); + + m_blockInfos.clear(); + m_functionBlockInfos.clear(); + m_blockSuccessors.clear(); + + { + // First we find all the blocks in the function, we add to the map + // and initialize the functionBlockInfos, which hold information about blocks that is constant across a function + // We will associate successors too, but we can only do this once we have set up the map + Index index = 0; + for (auto block : func->getChildren()) + { + IRBlock* blockInst = as<IRBlock>(block); + m_blockIndexMap.Add(blockInst, BlockIndex(index++)); + + FunctionBlockInfo functionBlockInfo; + functionBlockInfo.init(blockInst); + + m_functionBlockInfos.add(functionBlockInfo); + } + + // Allocate space for the root block infos + m_blockInfos.setCount(index); + + // Now we have the map, work out the successors as BlockIndex for each block + // and add those to m_blockSuccessors. They are indexed via successorsIndex/Count in the FunctionBlockInfos + for (auto& info : m_functionBlockInfos) + { + auto block = info.block; + + // Add all the successors + auto successors = block->getSuccessors(); + + const Index successorsStart = m_blockSuccessors.getCount(); + const Count successorsCount = successors.getCount(); + + info.successorsStart = successorsStart; + info.successorsCount = successorsCount; + + m_blockSuccessors.setCount(successorsStart + successorsCount); + + BlockIndex* dst = m_blockSuccessors.getBuffer() + successorsStart; + + for (auto successor : successors) + { + *dst++ = m_blockIndexMap[successor]; + } + } + } + + // Find the run of locations that all access the same root + Index start = 0; + while (start < count) + { + SLANG_ASSERT(locations[start].function == func); + + // Get the root at the start of this span + IRInst*const root = locations[start].root; + + // Look for the end of the run of locations with the same root + Index end = start + 1; + for (; end < count && locations[end].root == root; ++end); + + // Process the root + _processRoot(locations + start, end - start); + + // Set start to the beginning of the next run + start = end; + } +} + +void LivenessContext::processLocations(const List<Location>& inLocations) +{ + // Make a copy of all the locations + List<Location> locations(inLocations); + + // Sort so we have in function order, and within a function in root order + locations.sort([&](const Location& a, const Location& b) -> bool { return a.function < b.function || (a.function == b.function && a.root < b.root); }); + + const auto locationCount = locations.getCount(); + + Index start = 0; + while (start < locationCount) + { + auto func = locations[start].function; + Index end = start + 1; + + for (;end < locationCount && locations[end].function == func; ++end); + + // All of the locations from [start, end) are in the same function. Lets process all in one go... + _processLocationsInFunction(locations.getBuffer() + start, end - start); + + // Look for next run + start = end; + } +} + +} // anonymous + +static void _processFunction(IRFunc* funcInst, List<LivenessLocation>& ioLocations) { // If it has no body, then we are done if (funcInst->getFirstBlock() == nullptr) @@ -512,8 +1056,6 @@ void LivenessContext::_processFunction(IRFunc* funcInst) return; } - List<RootInfo> rootInfos; - // Iterate through blocks in the function, looking for variables to live track for (auto block = funcInst->getFirstBlock(); block; block = block->getNextBlock()) { @@ -522,38 +1064,25 @@ void LivenessContext::_processFunction(IRFunc* funcInst) // 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); + LivenessLocation location; - // Add as a root - RootInfo rootInfo; - rootInfo.root = varInst; - rootInfo.liveStart = liveStart; + location.function = funcInst; + // Set the livness start to be after the var + location.startLocation = IRInsertLoc::after(varInst); + location.root = varInst; - rootInfos.add(rootInfo); + ioLocations.add(location); } } } - - // Create the dominator tree. - m_dominatorTree = computeDominatorTree(funcInst); - - // Process the roots - for (const auto& rootInfo : rootInfos) - { - processRoot(rootInfo); - } } -void LivenessContext::processModule() +/* static */void LivenessUtil::locateVariables(IRModule* module, List<Location>& ioLocations) { // When we process liveness, is prior to output for a target // So post specialization - IRModuleInst* moduleInst = m_module->getModuleInst(); + IRModuleInst* moduleInst = module->getModuleInst(); for (IRInst* child : moduleInst->getChildren()) { @@ -562,18 +1091,15 @@ void LivenessContext::processModule() { // Then we want to look through their definition // inserting instructions that mark the liveness start/end - _processFunction(funcInst); + _processFunction(funcInst, ioLocations); } } } -} // anonymous - -void addLivenessTrackingToModule(IRModule* module) +/* static */void LivenessUtil::addLivenessRanges(IRModule* module, const List<Location>& inLocations) { LivenessContext context(module); - - context.processModule(); + context.processLocations(inLocations); } } // namespace Slang diff --git a/source/slang/slang-ir-liveness.h b/source/slang/slang-ir-liveness.h index 39098ae04..951af1793 100644 --- a/source/slang/slang-ir-liveness.h +++ b/source/slang/slang-ir-liveness.h @@ -2,11 +2,13 @@ #ifndef SLANG_IR_LIVENESS_H #define SLANG_IR_LIVENESS_H +#include "../core/slang-list.h" + +#include "slang-ir.h" + namespace Slang { -struct IRModule; - /* Liveness @@ -161,8 +163,23 @@ Similarly calling into a function could return a struct that contains fields whi fully specialized. */ - /// Adds LiveRangeStart and LiveRangeEnd instructions to demark the start and end of the liveness of a variable. -void addLivenessTrackingToModule(IRModule* module); +struct LivenessLocation +{ + IRGlobalValueWithCode* function; ///< The function the associated with this location + IRInst* root; ///< The root variable that is being liveness tracked + IRInsertLoc startLocation; ///< The location to insert start +}; + +struct LivenessUtil +{ + typedef LivenessLocation Location; + + /// Locate all of the variables across the module and append their locations into ioLocations + static void locateVariables(IRModule* module, List<Location>& ioLocations); + + /// Adds LiveRangeStart and LiveRangeEnd instructions to demark the start and end of the liveness of a variable, based on tlocations + static void addLivenessRanges(IRModule* module, const List<Location>& locations); +}; } diff --git a/source/slang/slang-ir.cpp b/source/slang/slang-ir.cpp index f4add4efc..9de2f5b4f 100644 --- a/source/slang/slang-ir.cpp +++ b/source/slang/slang-ir.cpp @@ -5842,6 +5842,10 @@ namespace Slang case kIROp_Block: return false; + /// Liveness markers have no side effects + case kIROp_LiveRangeStart: + case kIROp_LiveRangeEnd: + case kIROp_Nop: case kIROp_undefined: case kIROp_DefaultConstruct: |