diff options
| author | Ellie Hermaszewska <ellieh@nvidia.com> | 2024-10-29 14:49:26 +0800 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-10-29 14:49:26 +0800 |
| commit | f65d756bff8d4c5cbc15bd0322a2ae8e6b896a21 (patch) | |
| tree | ea1d61342cd29368e19135000ec2948813096205 /source/slang/slang-ir-liveness.cpp | |
| parent | a729c15e9dce9f5116a38afc66329ab2ca4cea54 (diff) | |
format
* format
* Minor test fixes
* enable checking cpp format in ci
Diffstat (limited to 'source/slang/slang-ir-liveness.cpp')
| -rw-r--r-- | source/slang/slang-ir-liveness.cpp | 611 |
1 files changed, 338 insertions, 273 deletions
diff --git a/source/slang/slang-ir-liveness.cpp b/source/slang/slang-ir-liveness.cpp index 28cd64a08..46d307f7f 100644 --- a/source/slang/slang-ir-liveness.cpp +++ b/source/slang/slang-ir-liveness.cpp @@ -1,15 +1,14 @@ #include "slang-ir-liveness.h" +#include "slang-ir-dominators.h" #include "slang-ir-insts.h" #include "slang-ir.h" -#include "slang-ir-dominators.h" - namespace Slang { -/* -Discussion +/* +Discussion ========== * We don't need to care about extractField / extractElement, as they only work directly on the value @@ -17,12 +16,12 @@ Discussion * 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.. +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 @@ -33,8 +32,8 @@ 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. +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. ``` @@ -74,21 +73,31 @@ Produces something like... 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. +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 +namespace +{ // anonymous /* A helper class to enable using a backing array, used in a stack like manner. */ -template <typename T> +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); } + 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); + } void setCount(Count count) { m_list->setCount(m_startIndex + count); } Count getCount() const { return m_list->getCount() - m_startIndex; } @@ -96,16 +105,12 @@ public: T& operator[](Index i) { return (*m_list)[m_startIndex + i]; } const T& operator[](Index i) const { return (*m_list)[m_startIndex + i]; } - RAIIStackArray(List<T>* list): - m_startIndex(list->getCount()), - m_list(list) + RAIIStackArray(List<T>* list) + : m_startIndex(list->getCount()), m_list(list) { SLANG_ASSERT(list); } - ~RAIIStackArray() - { - m_list->setCount(m_startIndex); - } + ~RAIIStackArray() { m_list->setCount(m_startIndex); } const Index m_startIndex; List<T>* m_list; @@ -113,42 +118,47 @@ public: struct LivenessContext { - enum class BlockIndex : Index { Invalid = -1 }; + enum class BlockIndex : Index + { + Invalid = -1 + }; - // NOTE! Care must be taken changing the order. + // 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 + 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(BlockResult from, BlockResult to) { return (from == BlockResult::NotVisited) || (Index(to) <= Index(from) && from != BlockResult::NotDominated); } + /// True if a result can be premoted `from` to `to` + static bool canPromote(BlockResult from, BlockResult to) + { + return (from == BlockResult::NotVisited) || + (Index(to) <= Index(from) && from != BlockResult::NotDominated); + } 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) + None, ///< There is no access + Alias, ///< Produces an alias to the root + Access, ///< Is an access to the root (perhaps through an alias) }; - - /// Block info (indexed via BlockIndex), that is valid across analysing liveness of a root + + /// Block info (indexed via BlockIndex), that is valid across analysing liveness of a root struct BlockInfo { - /// Reset any information for a start - void resetForStart() - { - result = BlockResult::NotVisited; - } + /// Reset any information for a start + void resetForStart() { result = BlockResult::NotVisited; } - /// Reset any information needed for a new root - void resetForRoot() + /// Reset any information needed for a new root + void resetForRoot() { resetForStart(); @@ -159,16 +169,17 @@ struct LivenessContext } // These are reset for *each* liveness start - BlockResult result; ///< The result for this block + BlockResult result; ///< The result for this block // These remain constant for all live starts to a root. - 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 + 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 }; - /// Block info (indexed via BlockIndex), that is fixed across a function + /// Block info (indexed via BlockIndex), that is fixed across a function struct FixedBlockInfo { void init(IRBlock* inBlock) @@ -183,165 +194,184 @@ struct LivenessContext bool isLoopStart() const { return breakBlockIndex != BlockIndex::Invalid; } - IRBlock* block; ///< The block + IRBlock* block; ///< The block - BlockIndex breakBlockIndex; ///< If this block terminates in a loop holds the break block - BlockIndex targetBlockIndex; ///< If this block terminates in a loop holds the target block + BlockIndex breakBlockIndex; ///< If this block terminates in a loop holds the break block + BlockIndex targetBlockIndex; ///< If this block terminates in a loop holds the target block - BlockIndex owningLoopBlockIndex;///< The loop this block 'belongs' to (or Invalid if doesn't belong to a loop) + BlockIndex owningLoopBlockIndex; ///< The loop this block 'belongs' to (or Invalid if + ///< doesn't belong to a loop) - Index successorsStart; ///< Indexes into block successors - Count successorsCount; ///< How many successors + Index successorsStart; ///< Indexes into block successors + Count successorsCount; ///< How many successors }; struct Loop { - const Loop* parentLoop; ///< The parent loop, which will be entered when this loop is left via a break - BlockIndex targetBlockIndex; ///< The target block for this loop - BlockIndex breakBlockIndex; ///< The break block for this loop - BlockIndex loopBlockIndex; ///< Block id that terminates with loop we are currently in + const Loop* parentLoop; ///< The parent loop, which will be entered when this loop is left + ///< via a break + BlockIndex targetBlockIndex; ///< The target block for this loop + BlockIndex breakBlockIndex; ///< The break block for this loop + BlockIndex loopBlockIndex; ///< Block id that terminates with loop we are currently in }; - /// Process the module + /// Process the module void process(); - - LivenessContext(IRModule* module, LivenessMode mode): - m_module(module), - m_livenessMode(mode), - m_builder(module) + + LivenessContext(IRModule* module, LivenessMode mode) + : m_module(module), m_livenessMode(mode), m_builder(module) { // Disable warning if not used SLANG_UNUSED(&LivenessContext::_isAnyRunInst); } - /// 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. + /// 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. + /// Process a successor to a block + /// Can only be called after a call to _findAliasesAndAccesses for the root. BlockResult _processSuccessor(BlockIndex blockIndex, const Loop* loop); - /// Process a block - /// Can only be called after a call to _findAliasesAndAccesses for the root. - BlockResult _processBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run, const Loop* loop); + /// Process a block + /// Can only be called after a call to _findAliasesAndAccesses for the root. + BlockResult _processBlock( + BlockIndex blockIndex, + const ConstArrayView<IRInst*>& run, + const Loop* loop); - /// Process all the locations in the function - /// NOTE: All locations must be to the same function, and ordered by root. + /// Process all the locations in the function + /// NOTE: All locations must be to the same function, and ordered by root. void _processFunction(IRFunc* func); - /// Process a root - /// NOTE: All starts must be to the same root/referenced item - void _processRoot(IRLiveRangeStart*const* starts, Count count); + /// Process a root + /// NOTE: All starts must be to the same root/referenced item + void _processRoot(IRLiveRangeStart* const* starts, Count count); - /// Find all the aliases and accesses to the root - /// The information is stored in m_accessSet and m_aliases + /// 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 if there is already a result + /// Add a result for the block + /// 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. + /// 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 + /// Adds an instruction that is an access to the root void _addAccessInst(IRInst* inst); - /// Add a live range start + /// 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 + /// 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 + /// True if it's an instruction of interest and so will go within a run for a block bool _isNormalRunInst(IRInst* inst); - /// Returns true if is a normal run inst, or if is a return that accesses + /// Returns true if is a normal run inst, or if is a return that accesses bool _isAnyRunInst(IRInst* inst); - // Returns the index in the run of a start for the current root, else -1 + // 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 a load-like access, else -1 + /// Returns the last index within the run which is a load-like access, else -1 Index _findLastLoadLike(const ConstArrayView<IRInst*>& run); - /// Adds an LiveRangeEnd for the root after `inst` if there isn't one there already + /// Adds an LiveRangeEnd for the root after `inst` if there isn't one there already void _maybeAddEndAfterInst(IRInst* inst); void _maybeAddEndBeforeInst(IRInst* inst); - /// Maybe insert an end after the instruction - void _maybeAddEndAfterRunIndex(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run, Index runIndex); + /// Maybe insert an end after the instruction + void _maybeAddEndAfterRunIndex( + BlockIndex blockIndex, + const ConstArrayView<IRInst*>& run, + Index runIndex); - // Add a live end instruction at the start of block, referencing the root + // Add a live end instruction at the start of block, referencing the root void _maybeAddEndAtBlockStart(BlockIndex blockIndex); - /// Look from inst for an LiveEndRange to the root. + /// 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 + /// 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 + /// Get block info BlockInfo* _getBlockInfo(BlockIndex blockIndex) { return &m_blockInfos[Index(blockIndex)]; } - /// Get block info fixed across a function being analyzed. - const FixedBlockInfo& _getFixedBlockInfo(BlockIndex blockIndex) const { return m_fixedBlockInfos[Index(blockIndex)]; } + /// Get block info fixed across a function being analyzed. + const FixedBlockInfo& _getFixedBlockInfo(BlockIndex blockIndex) const + { + return m_fixedBlockInfos[Index(blockIndex)]; + } - /// Get the block from the index - IRBlock* _getBlock(BlockIndex blockIndex) const { return m_fixedBlockInfos[Index(blockIndex)].block; } + /// Get the block from the index + IRBlock* _getBlock(BlockIndex blockIndex) const + { + return m_fixedBlockInfos[Index(blockIndex)].block; + } - /// True if the terminator can be considered an access - /// This allows us to elide a scope end if the root is returned + /// True if the terminator can be considered an access + /// This allows us to elide a scope end if the root is returned bool _isAccessTerminator(IRTerminatorInst* terminator); - /// Order the range starts in a deterministic manner + /// Order the range starts in a deterministic manner void _orderRangeStartsDeterministically(); - /// Remove any end/start spands within a block, that aren't 'interesting. + /// Remove any end/start spands within a block, that aren't 'interesting. void _tidyUninterestingSpans(); - /// Gets the instructions of interest for this info, in the order they appear within the block - ConstArrayView<IRInst*> _getRun(const BlockInfo* info) + /// 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(); + IRInst* const* buffer = m_instRuns.getBuffer(); return ConstArrayView<IRInst*>(buffer + info->runStart, info->runCount); } - /// Gets all of the successors for the blockIdnex + /// Gets all of the successors for the blockIdnex ConstArrayView<BlockIndex> _getSuccessors(BlockIndex blockIndex) { const auto& info = m_fixedBlockInfos[Index(blockIndex)]; - return makeConstArrayView(m_blockSuccessors.getBuffer() + info.successorsStart, info.successorsCount); + return makeConstArrayView( + m_blockSuccessors.getBuffer() + info.successorsStart, + info.successorsCount); } - /// Determine which loops blocks 'belong' to. The owning block is the block that *contains* the - /// loop instruction as it's terminator. + /// Determine which loops blocks 'belong' to. The owning block is the block that *contains* the + /// loop instruction as it's terminator. void _calcLoopOwnership(); - RefPtr<IRDominatorTree> m_dominatorTree; ///< The dominator tree for the current function + 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 - 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 - IRInst* m_root = nullptr; ///< The current root - IRBlock* m_rootBlock = nullptr; ///< The block the root is in - - List<BlockResult> m_successorResults; ///< Storage for successor results + 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 - HashSet<IRInst*> m_accessSet; ///< If instruction is in set it is an `access` indicating it must be live at least up to this instruction + 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<FixedBlockInfo> m_fixedBlockInfos; ///< Information about blocks across the current function - List<BlockIndex> m_blockSuccessors; ///< Successors for a blocks, accessed via FixedBlockInfo + 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<FixedBlockInfo> + m_fixedBlockInfos; ///< Information about blocks across the current function + List<BlockIndex> m_blockSuccessors; ///< Successors for a blocks, accessed via FixedBlockInfo - List<IRInst*> m_instRuns; ///< Instructions of interest in order. Indexed into via BlockInfo [runStart, runStart + runCount) + List<IRInst*> m_instRuns; ///< Instructions of interest in order. Indexed into via BlockInfo + ///< [runStart, runStart + runCount) - List<IRLiveRangeStart*> m_rangeStarts; ///< All the starts within a function, ordered by referenced - List<IRLiveRangeEnd*> m_rangeEnds; ///< All of the ends added + List<IRLiveRangeStart*> + m_rangeStarts; ///< All the starts within a function, ordered by referenced + List<IRLiveRangeEnd*> m_rangeEnds; ///< All of the ends added IRModule* m_module; IRBuilder m_builder; @@ -390,12 +420,15 @@ void LivenessContext::_maybeAddEndAtBlockStart(BlockIndex blockIndex) // 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 + // 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); } -LivenessContext::BlockResult LivenessContext::_addBlockResult(BlockIndex blockIndex, BlockResult result) +LivenessContext::BlockResult LivenessContext::_addBlockResult( + BlockIndex blockIndex, + BlockResult result) { auto& currentResult = _getBlockInfo(blockIndex)->result; // Check we can promote @@ -404,36 +437,38 @@ LivenessContext::BlockResult LivenessContext::_addBlockResult(BlockIndex blockIn return result; } -LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex blockIndex, const Loop* loop) +LivenessContext::BlockResult LivenessContext::_processSuccessor( + BlockIndex blockIndex, + const Loop* loop) { auto blockInfo = _getBlockInfo(blockIndex); - - // Check if there is already a result for this block. + + // Check if there is already a result for this block. // If there is just return that. auto result = blockInfo->result; switch (result) { - case BlockResult::NotVisited: + case BlockResult::NotVisited: { // If not visited we need to process break; } - case BlockResult::Visited: + 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. + // 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 + + // 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) + // 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 @@ -451,20 +486,24 @@ LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex block // meaning the root *must* be live on the looping. // TODO(JS): - // The solution used here is somewhat conservative, it assumes if a branch back to the start of the loop can be reached that + // The solution used here is somewhat conservative, it assumes if a branch back to + // the start of the loop can be reached that // // * There might be some path where the loop might exit - // * There might be some path where the root(variable or alias) may be loaded/or stored + // * There might be some path where the root(variable or alias) may be loaded/or + // stored // // If these assumptions are wrong it will lead to // // * Potentially a liveness end that is never hit(outside of the loop) - // * Potentially liveness for a root that spans across the loop even if that is not actually necessary - // - // This could be improved on but would probably need something like 'loop analysis' that specially determined - // those scenarios, such that the assumptions aren't needed. It would need to be 'separate analysis', because - // the liveness traversal is a kind of incremental depth first traversal. But for loop analysis it would require - // at loop start the result on all paths through the loop. + // * Potentially liveness for a root that spans across the loop even if that is not + // actually necessary + // + // This could be improved on but would probably need something like 'loop analysis' + // that specially determined those scenarios, such that the assumptions aren't + // needed. It would need to be 'separate analysis', because the liveness traversal + // is a kind of incremental depth first traversal. But for loop analysis it would + // require at loop start the result on all paths through the loop. const auto breakBlockIndex = loop->breakBlockIndex; @@ -472,7 +511,7 @@ LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex block result = _processSuccessor(breakBlockIndex, loop->parentLoop); if (result != BlockResult::Found) { - // If an end is not found from the break, + // If an end is not found from the break, // we just insert an end at the start of the break block _maybeAddEndAtBlockStart(breakBlockIndex); @@ -485,7 +524,7 @@ LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex block // Otherwise just return result return result; } - default: + default: { // Otherwise just return result return result; @@ -494,8 +533,8 @@ LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex block const auto block = _getBlock(blockIndex); - // If the block is *not* dominated by the root block, we know it can't - // end liveness. + // 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)) { @@ -505,8 +544,9 @@ LivenessContext::BlockResult LivenessContext::_processSuccessor(BlockIndex block // Mark that it is visited _addBlockResult(blockIndex, BlockResult::Visited); - // Special case leaving the loop. - // If we are in a loop, and the block we are going to is the break block then we are no longer in this loop + // Special case leaving the loop. + // If we are in a loop, and the block we are going to is the break block then we are no longer + // in this loop if (loop && loop->breakBlockIndex == blockIndex) { // We are in the parent loop @@ -571,7 +611,10 @@ IRInst* LivenessContext::_findRootEnd(IRInst* inst) return nullptr; } -void LivenessContext::_maybeAddEndAfterRunIndex(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run, Index runIndex) +void LivenessContext::_maybeAddEndAfterRunIndex( + BlockIndex blockIndex, + const ConstArrayView<IRInst*>& run, + Index runIndex) { SLANG_UNUSED(blockIndex); return _maybeAddEndAfterInst(run[runIndex]); @@ -580,11 +623,10 @@ void LivenessContext::_maybeAddEndAfterRunIndex(BlockIndex blockIndex, const Con void LivenessContext::_maybeAddEndAfterInst(IRInst* inst) { // We can't add after the inst, if it's a terminator - // or if we find an end. - if (as<IRTerminatorInst>(inst) == nullptr && - !_findRootEnd(inst->getNextInst())) + // or if we find an end. + if (as<IRTerminatorInst>(inst) == nullptr && !_findRootEnd(inst->getNextInst())) { - // Just add end of scope after the inst + // Just add end of scope after the inst m_builder.setInsertLoc(IRInsertLoc::after(inst)); // Add the live end inst m_rangeEnds.add(m_builder.emitLiveRangeEnd(m_root)); @@ -595,14 +637,16 @@ void LivenessContext::_maybeAddEndBeforeInst(IRInst* inst) { if (!_findRootEnd(inst)) { - // Just add end of scope after the inst + // Just add end of scope after the inst m_builder.setInsertLoc(IRInsertLoc::before(inst)); // Add the live end inst m_rangeEnds.add(m_builder.emitLiveRangeEnd(m_root)); } } -LivenessContext::BlockResult LivenessContext::_completeBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run) +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); @@ -614,7 +658,7 @@ LivenessContext::BlockResult LivenessContext::_completeBlock(BlockIndex blockInd if (lastLoadLikeIndex >= 0) { _maybeAddEndAfterRunIndex(blockIndex, run, lastLoadLikeIndex); - + // Add the result return _addBlockResult(blockIndex, BlockResult::Found); } @@ -633,10 +677,13 @@ static IRLoop* _getLoopTerminator(IRBlock* block) return nullptr; } -LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockIndex, const ConstArrayView<IRInst*>& run, const Loop* loop) +LivenessContext::BlockResult LivenessContext::_processBlock( + BlockIndex blockIndex, + const ConstArrayView<IRInst*>& run, + const Loop* loop) { // 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 @@ -644,12 +691,12 @@ LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockInde // Since this is the case, we know start is not part of the run SLANG_ASSERT(run.indexOf(m_rootLiveStart) < 0); - // 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 + // 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. + // 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) { @@ -663,9 +710,9 @@ LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockInde const Index successorCount = successors.getCount(); - // 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. + // 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. // Set up space to store successor results RAIIStackArray<BlockResult> successorResults(&m_successorResults); @@ -687,7 +734,7 @@ LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockInde for (Index i = 0; i < successorCount; ++i) { const auto result = _processSuccessor(successors[i], &nextLoop); - successorResults[i] = result; + successorResults[i] = result; } } else @@ -701,7 +748,7 @@ LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockInde } // Zero initialize all the counts - Index foundCounts[Index(BlockResult::CountOf)] = { 0 }; + Index foundCounts[Index(BlockResult::CountOf)] = {0}; for (const auto successorResult : successorResults.getConstView()) { // Change counts depending on the result @@ -738,7 +785,7 @@ LivenessContext::BlockResult LivenessContext::_processBlock(BlockIndex blockInde } } - // This block, can now be marked as found + // This block, can now be marked as found return _addBlockResult(blockIndex, BlockResult::Found); } @@ -760,8 +807,8 @@ void LivenessContext::_addInst(IRInst* inst) // 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. + // 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; } @@ -772,7 +819,7 @@ void LivenessContext::_addAccessInst(IRInst* inst) { return; } - + // Add to the access set m_accessSet.add(inst); @@ -789,18 +836,21 @@ void LivenessContext::_findAliasesAndAccesses(IRInst* 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 + + // 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. // - // 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. + // 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 + // 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 @@ -826,35 +876,38 @@ void LivenessContext::_findAliasesAndAccesses(IRInst* root) // We want to find instructions that access the root switch (cur->getOp()) { - case kIROp_GetElementPtr: + case kIROp_GetElementPtr: { base = static_cast<IRGetElementPtr*>(cur)->getBase(); accessType = AccessType::Alias; break; } - case kIROp_FieldAddress: + case kIROp_FieldAddress: { base = static_cast<IRFieldAddress*>(cur)->getBase(); accessType = AccessType::Alias; break; } - case kIROp_GetAddr: + case kIROp_GetAddr: { IRGetAddress* getAddr = static_cast<IRGetAddress*>(cur); base = getAddr->getOperand(0); accessType = AccessType::Alias; break; } - case kIROp_Call: + 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. + // 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, + // * 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` @@ -864,48 +917,50 @@ void LivenessContext::_findAliasesAndAccesses(IRInst* root) accessType = AccessType::Access; break; } - case kIROp_Load: + case kIROp_Load: { - // We normally only care about loads in terms of identifying liveness within a block - // the last load being the last necessay live point. + // We normally only care about loads in terms of identifying liveness within a + // block the last load being the last necessay live point. base = static_cast<IRLoad*>(cur)->getPtr(); accessType = AccessType::Access; break; } - case kIROp_Store: + case kIROp_Store: { // We need stores for loop analysis base = static_cast<IRStore*>(cur)->getPtr(); accessType = AccessType::Access; break; } - case kIROp_GetElement: - case kIROp_FieldExtract: + case kIROp_GetElement: + case kIROp_FieldExtract: { - // These will never take place on the var which is accessed through a pointer, so can be ignored + // These will never take place on the var which is accessed through a pointer, + // so can be ignored break; } - - default: break; + + default: break; } - // Make sure the access is through the alias (as opposed to some other part of the instructions 'use') + // 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: + case AccessType::Alias: { // Add this instruction to the aliases m_aliases.add(cur); break; } - case AccessType::Access: + case AccessType::Access: { _addAccessInst(cur); break; } - default: break; + default: break; } } } @@ -926,7 +981,7 @@ void LivenessContext::_findAndEmitRangeEnd(IRLiveRangeStart* liveRangeStart) // 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 @@ -934,16 +989,18 @@ void LivenessContext::_findAndEmitRangeEnd(IRLiveRangeStart* liveRangeStart) // 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_blockResults + // 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_blockResults + // + // There is an extra caveat around the dominator tree. In principal a variable in block A is + // accessible by any block that is dominated by A. It's actually more restricted than this - + // because IR has other rules that provide more tight scoping. The extra information can be seen + // in a loop instruction also indicating the break and continue blocks. // - // There is an extra caveat around the dominator tree. In principal a variable in block A is accessible by any block that is - // dominated by A. It's actually more restricted than this - because IR has other rules that provide more tight scoping. - // The extra information can be seen in a loop instruction also indicating the break and continue blocks. - // - // If we just traversed the successors, if there is a loop we'd end up in an infinite loop. We can partly avoid this because - // we know that the root is only available in blocks dominated by the root. There is also the scenario where there is a loop - // in blocks within the dominator tree. That is handled by marking 'Visited' when a final result isn't known, but we want to + // If we just traversed the successors, if there is a loop we'd end up in an infinite loop. We + // can partly avoid this because we know that the root is only available in blocks dominated by + // the root. There is also the scenario where there is a loop in blocks within the dominator + // tree. That is handled by marking 'Visited' when a final result isn't known, but we want to // detect a loop. In most respect Visited behaves in the same manner as NotDominated. { @@ -991,11 +1048,9 @@ bool LivenessContext::_isNormalRunInst(IRInst* inst) // NOTE! // The ops in the list above are the only ops *currently* that indicate an access. // Has to be consistent with `_findAliasesAndAccesses` - if (op == kIROp_Call || - op == kIROp_Load || - op == kIROp_Store) + if (op == kIROp_Call || op == kIROp_Load || op == kIROp_Store) { - // Just because it's the right type *doesn't* mean it's an access, it has to also + // 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); } @@ -1006,7 +1061,7 @@ bool LivenessContext::_isNormalRunInst(IRInst* inst) bool LivenessContext::_isAccessTerminator(IRTerminatorInst* terminator) { // This is to special case when a return, returns a root or an alias - // + // // We need to detect if the return value accesses the root if (terminator->getOp() == kIROp_Return) @@ -1015,8 +1070,8 @@ bool LivenessContext::_isAccessTerminator(IRTerminatorInst* terminator) auto returnVal = static_cast<IRReturn*>(terminator); auto val = returnVal->getVal(); - - // TODO(JS): This is perhaps somewhat argable, but it means if + + // TODO(JS): This is perhaps somewhat argable, but it means if // we have a cast between uint/int (for example) that isn't a problem // Strip construct @@ -1029,9 +1084,7 @@ bool LivenessContext::_isAccessTerminator(IRTerminatorInst* terminator) case kIROp_CastIntToPtr: case kIROp_CastPtrToInt: case kIROp_CastPtrToBool: - case kIROp_PtrCast: - val = val->getOperand(0); - break; + case kIROp_PtrCast: val = val->getOperand(0); break; } // If it *is* the root it's an access @@ -1083,7 +1136,7 @@ void LivenessContext::_findInstRunsForBlocks() } else if (blockInfo->instCount == 1) { - // This is the easy case, since we don't need to determine the order of the instructions + // This is the easy case, since we don't need to determine the order of the instructions SLANG_ASSERT(blockInfo->lastInst); m_instRuns.add(blockInfo->lastInst); blockInfo->runCount = 1; @@ -1091,7 +1144,7 @@ void LivenessContext::_findInstRunsForBlocks() else { // TODO(JS): - // NOTE That we don't need to keep all accesses in the run, only the last accesses + // 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. @@ -1114,12 +1167,12 @@ void LivenessContext::_findInstRunsForBlocks() } } SLANG_ASSERT(dst == m_instRuns.end()); - } + } SLANG_ASSERT(blockInfo->runCount == blockInfo->instCount); - // Special case the terminator - we allow a return that accesses the root - // to be added to the run. + // Special case the terminator - we allow a return that accesses the root + // to be added to the run. // // TODO(JS): We might want this behavior to be switchable with an option. // If we don't add the terminator, everything else will behave correctly with regard @@ -1154,7 +1207,7 @@ void LivenessContext::_processRoot(IRLiveRangeStart* const* rangeStarts, Count r info.resetForRoot(); } m_instRuns.clear(); - + auto root = rangeStarts[0]->getReferenced(); // Set the root @@ -1255,7 +1308,8 @@ void LivenessContext::_calcLoopOwnership() continue; } // Check if already owned (must be by this loop) - const auto successorOwner = _getFixedBlockInfo(successorBlockIndex).owningLoopBlockIndex; + const auto successorOwner = + _getFixedBlockInfo(successorBlockIndex).owningLoopBlockIndex; if (successorOwner != BlockIndex::Invalid) { SLANG_ASSERT(successorOwner == loopBlockIndex); @@ -1285,9 +1339,10 @@ void LivenessContext::_processFunction(IRFunc* 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 + // 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(); @@ -1299,8 +1354,9 @@ void LivenessContext::_processFunction(IRFunc* func) { // 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 + // 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()) { @@ -1317,7 +1373,8 @@ void LivenessContext::_processFunction(IRFunc* func) 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 + // and add those to m_blockSuccessors. They are indexed via successorsIndex/Count in the + // FunctionBlockInfos for (auto& fixedInfo : m_fixedBlockInfos) { auto block = fixedInfo.block; @@ -1330,9 +1387,9 @@ void LivenessContext::_processFunction(IRFunc* func) fixedInfo.targetBlockIndex = m_blockIndexMap[loop->getTargetBlock()]; } - // Add all the successors + // Add all the successors auto successors = block->getSuccessors(); - + const Index successorsStart = m_blockSuccessors.getCount(); const Count successorsCount = successors.getCount(); @@ -1362,13 +1419,14 @@ void LivenessContext::_processFunction(IRFunc* func) { // Get the root at the start of this span const auto root = m_rangeStarts[start]->getReferenced(); - + // Look for the end of the run of locations with the same root Index end = start + 1; - for (; end < count && m_rangeStarts[end]->getReferenced() == root; ++end); + for (; end < count && m_rangeStarts[end]->getReferenced() == root; ++end) + ; - // Process the root - _processRoot(m_rangeStarts.getBuffer() + start, end - start); + // Process the root + _processRoot(m_rangeStarts.getBuffer() + start, end - start); // Set start to the beginning of the next run start = end; @@ -1392,12 +1450,13 @@ static bool _isRootTypeScalar(IRType* type) void LivenessContext::_tidyUninterestingSpans() { - // We are looking for spans from an end to a start for a scalar variable. + // We are looking for spans from an end to a start for a scalar variable. // Only scalar for now so even if the span is 'big' the cost is probably low. - // - // A more sophisticated implementation could perhaps look in the span if there is only a full store - // for a struct/large type. Would also need some concept of the 'amount of insts' to determine if worth it. - + // + // A more sophisticated implementation could perhaps look in the span if there is only a full + // store for a struct/large type. Would also need some concept of the 'amount of insts' to + // determine if worth it. + const Count count = m_rangeEnds.getCount(); for (Index i = 0; i < count; ++i) @@ -1410,14 +1469,14 @@ void LivenessContext::_tidyUninterestingSpans() { continue; } - + // Look for a start to the same root in the block // A more sophisticated implementation might try to look across unconditional branches - // but since only *one* end is stored for potentially multiple starts, and that a block + // but since only *one* end is stored for potentially multiple starts, and that a block // might have multiple predecessors, we ignore for now. IRLiveRangeStart* start = nullptr; for (auto cur = end->getNextInst(); cur; cur = cur->getNextInst()) - { + { // If it's a start if (auto foundStart = as<IRLiveRangeStart>(cur)) { @@ -1429,7 +1488,7 @@ void LivenessContext::_tidyUninterestingSpans() } } } - + // If we found a matching start, lets just remove the span if (start) { @@ -1458,19 +1517,21 @@ void LivenessContext::_orderRangeStartsDeterministically() return; } - // The fast way is to just order by the roots pointers. + // The fast way is to just order by the roots pointers. // Unfortunately that is unstable, as it depends on the allocation location which varies. // Sort into referenced/root start - //m_rangeStarts.sort([&](IRLiveRangeStart* a, IRLiveRangeStart* b) -> bool { return a->getReferenced() < b->getReferenced(); }); + // m_rangeStarts.sort([&](IRLiveRangeStart* a, IRLiveRangeStart* b) -> bool { return + // a->getReferenced() < b->getReferenced(); }); - // The order that the starts is *found* is deterministic, so we'll use that as part of the key to sort. + // The order that the starts is *found* is deterministic, so we'll use that as part of the key + // to sort. struct Entry { IRLiveRangeStart* start; - Index foundIndex; ///< The found index - Index rootIndex; ///< Index for the root + Index foundIndex; ///< The found index + Index rootIndex; ///< Index for the root }; Int orderCounter = 0; @@ -1501,7 +1562,12 @@ void LivenessContext::_orderRangeStartsDeterministically() } // Sort by the root indices and if equal sort by the found order - entries.sort([&](const Entry& a, const Entry& b) -> bool { return (a.rootIndex < b.rootIndex) || (a.rootIndex == b.rootIndex && a.foundIndex < b.foundIndex); }); + entries.sort( + [&](const Entry& a, const Entry& b) -> bool + { + return (a.rootIndex < b.rootIndex) || + (a.rootIndex == b.rootIndex && a.foundIndex < b.foundIndex); + }); // Copy back for (Index i = 0; i < rangeStartsCount; ++i) @@ -1535,7 +1601,7 @@ void LivenessContext::process() } } -} // anonymous +} // namespace static void _processFunction(IRFunc* funcInst, List<IRVar*>& ioVars) { @@ -1554,13 +1620,12 @@ static void _processFunction(IRFunc* funcInst, List<IRVar*>& ioVars) if (auto varInst = as<IRVar>(inst)) { ioVars.add(varInst); - } } } } -/* static */void LivenessUtil::addVariableRangeStarts(IRModule* module, LivenessMode livenessMode) +/* static */ void LivenessUtil::addVariableRangeStarts(IRModule* module, LivenessMode livenessMode) { if (!isEnabled(livenessMode)) { @@ -1596,7 +1661,7 @@ static void _processFunction(IRFunc* funcInst, List<IRVar*>& ioVars) } } -/* static */void LivenessUtil::addRangeEnds(IRModule* module, LivenessMode livenessMode) +/* static */ void LivenessUtil::addRangeEnds(IRModule* module, LivenessMode livenessMode) { if (isEnabled(livenessMode)) { |
