Remove LivenessLocation (#2248)

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

* Remove the need for LivenessLocation.

* Use LivenessMode.

* Fix some comments.

Co-authored-by: Yong He <yonghe@outlook.com>

5 files changed, 170 insertions, 135 deletions

diff --git a/source/slang/slang-emit.cpp b/source/slang/slang-emit.cpp
index a128644d3..0ed17ad7c 100644
--- a/source/slang/slang-emit.cpp
+++ b/source/slang/slang-emit.cpp
@@ -736,10 +736,9 @@ Result linkAndOptimizeIR(
     simplifyIR(irModule);
 
     {
-        // Storage for liveness information
-        List<LivenessLocation> livenessLocations;
-        const bool shouldTrackLiveness = codeGenContext->shouldTrackLiveness();
-
+        // Get the liveness mode.
+        const LivenessMode livenessMode = codeGenContext->shouldTrackLiveness() ? LivenessMode::Enabled : LivenessMode::Disabled;
+        
         //
         // Downstream targets may benefit from having live-range information for
         // local variables, and our IR currently encodes a reasonably good version
@@ -750,9 +749,9 @@ Result linkAndOptimizeIR(
         // temporary variables into the IR module should take responsibility for
         // producing their own live-range information.
         //
-        if (shouldTrackLiveness)
+        if (isEnabled(livenessMode))
         {
-            LivenessUtil::locateVariables(irModule, livenessLocations);
+            LivenessUtil::addVariableRangeStarts(irModule, livenessMode);
         }
 
         // As a late step, we need to take the SSA-form IR and move things *out*
@@ -764,9 +763,7 @@ Result linkAndOptimizeIR(
 
         {
             // We only want to accumulate locations if liveness tracking is enabled.
-            List<LivenessLocation>* locsPtr = shouldTrackLiveness ? &livenessLocations : nullptr;
-
-            eliminatePhis(codeGenContext, locsPtr, irModule);
+            eliminatePhis(codeGenContext, livenessMode, irModule);
 #if 0
             dumpIRIfEnabled(codeGenContext, irModule, "PHIS ELIMINATED");
 #endif
@@ -774,9 +771,9 @@ Result linkAndOptimizeIR(
 
         // If liveness is enabled add liveness ranges based on the accumulated liveness locations
 
-        if (shouldTrackLiveness)
+        if (isEnabled(livenessMode))
         {
-            LivenessUtil::addLivenessRanges(irModule, livenessLocations);
+            LivenessUtil::addRangeEnds(irModule, livenessMode);
 
 #if 0
             dumpIRIfEnabled(codeGenContext, irModule, "LIVENESS");
diff --git a/source/slang/slang-ir-eliminate-phis.cpp b/source/slang/slang-ir-eliminate-phis.cpp
index ab26bb8eb..9aac7de3a 100644
--- a/source/slang/slang-ir-eliminate-phis.cpp
+++ b/source/slang/slang-ir-eliminate-phis.cpp
@@ -68,14 +68,14 @@ struct PhiEliminationContext
     IRModule* m_module = nullptr;
     SharedIRBuilder m_sharedBuilder;
     IRBuilder m_builder;
-    List<LivenessLocation>* m_livenessLocations;
+    LivenessMode m_livenessMode;
 
-    PhiEliminationContext(CodeGenContext* codeGenContext, List<LivenessLocation>* ioLivenessLocations, IRModule* module)
+    PhiEliminationContext(CodeGenContext* codeGenContext, LivenessMode livenessMode, IRModule* module)
         : m_codeGenContext(codeGenContext)
         , m_module(module)
         , m_sharedBuilder(module)
         , m_builder(m_sharedBuilder)
-        , m_livenessLocations(ioLivenessLocations)
+        , m_livenessMode(livenessMode)
     {}
 
     // We start with the top-down logic of the pass, which is to process
@@ -786,36 +786,31 @@ struct PhiEliminationContext
                 return;
             }
 
-            // When we have an assignment that is ready to perform,
-            // we do so by storing the value of the corresponding
-            // argument into the temporary for the coresponding
-            // parameter.
-            //
-            // Note that we use `actualValPtr` here instead of `originalVal`,
-            // so that any logic that might have moved another parameter
-            // into a temporary will influence our result.
-            //
             auto& dstParam = assignment.param;
             auto& srcArg = assignment.arg;
-            auto storeInst = m_builder.emitStore(dstParam.temp, *srcArg.currentValPtr);
 
-            // If we have liveness tracking add the location
-            if (m_livenessLocations)
+            // If we have liveness tracking add the start location.
+            if (isEnabled(m_livenessMode))
             {
-                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);
+                m_builder.emitLiveRangeStart(dstParam.temp);
             }
 
+            // When we have an assignment that is ready to perform,
+            // we do so by storing the value of the corresponding
+            // argument into the temporary for the coresponding
+            // parameter.
+            //
+            // Note that we use `actualValPtr` here instead of `originalVal`,
+            // so that any logic that might have moved another parameter
+            // into a temporary will influence our result.
+            //
+            m_builder.emitStore(dstParam.temp, *srcArg.currentValPtr);
+
             //
             // Once the store is emitted, the assignment has been performed,
             // and it can move to the _done_ state.
@@ -905,9 +900,9 @@ struct PhiEliminationContext
     }
 };
 
-void eliminatePhis(CodeGenContext* codeGenContext, List<LivenessLocation>* ioLocations, IRModule* module)
+void eliminatePhis(CodeGenContext* codeGenContext, LivenessMode livenessMode, IRModule* module)
 {
-    PhiEliminationContext context(codeGenContext, ioLocations, module);
+    PhiEliminationContext context(codeGenContext, livenessMode, module);
     context.eliminatePhisInModule();
 }
 
diff --git a/source/slang/slang-ir-eliminate-phis.h b/source/slang/slang-ir-eliminate-phis.h
index 90eb485e1..b21363cc8 100644
--- a/source/slang/slang-ir-eliminate-phis.h
+++ b/source/slang/slang-ir-eliminate-phis.h
@@ -14,7 +14,6 @@ namespace Slang
         /// so that it is more suitable for emission on targets that
         /// are not themselves based on an SSA representation.
         ///
-        /// 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);
+        /// If livenessMode is enabled LiveRangeStarts will be inserted into the module.
+    void eliminatePhis(CodeGenContext* context, LivenessMode livenessMode, IRModule* module);
 }
diff --git a/source/slang/slang-ir-liveness.cpp b/source/slang/slang-ir-liveness.cpp
index 05fccbe43..81de6d6c2 100644
--- a/source/slang/slang-ir-liveness.cpp
+++ b/source/slang/slang-ir-liveness.cpp
@@ -112,8 +112,6 @@ public:
 
 struct LivenessContext
 {
-    typedef LivenessLocation Location;
-
     enum class BlockIndex : Index;
 
     // NOTE! Care must be taken changing the order. 
@@ -177,11 +175,12 @@ struct LivenessContext
         Count successorsCount;
     };
 
-        /// Process all the locations
-    void processLocations(const List<Location>& locations);
+        /// Process the module
+    void process();
     
-    LivenessContext(IRModule* module):
-        m_module(module)
+    LivenessContext(IRModule* module, LivenessMode mode):
+        m_module(module),
+        m_livenessMode(mode)
     {
         // Disable warning if not used
         SLANG_UNUSED(&LivenessContext::_isAnyRunInst);
@@ -204,11 +203,11 @@ struct LivenessContext
 
         /// 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);
+    void _processFunction(IRFunc* func);
 
         /// Process a root
-        /// NOTE: All locations must be to the same root
-    void _processRoot(const Location* locations, Count count);
+        /// 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
@@ -303,13 +302,51 @@ struct LivenessContext
 
     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
+    List<IRLiveRangeStart*> m_rangeStarts;          ///< All the starts within a function, ordered by referenced
 
     IRModule* m_module;
     SharedIRBuilder m_sharedBuilder;
     IRBuilder m_builder;
+
+    LivenessMode m_livenessMode;
 };
 
+static void _findLiveStarts(IRFunc* funcInst, List<IRLiveRangeStart*>& ioStarts)
+{
+    // If it has no body, then we are done
+    if (funcInst->getFirstBlock() == nullptr)
+    {
+        return;
+    }
+
+    // Iterate through blocks looking for start
+    for (auto block = funcInst->getFirstBlock(); block; block = block->getNextBlock())
+    {
+        for (auto inst = block->getFirstChild(); inst; inst = inst->getNextInst())
+        {
+            // We look for LiveRangeStarts
+            if (auto rangeStartInst = as<IRLiveRangeStart>(inst))
+            {
+                ioStarts.add(rangeStartInst);
+            }
+        }
+    }
+}
+
+static void _findFuncs(IRModule* module, List<IRFunc*>& ioFuncs)
+{
+    IRModuleInst* moduleInst = module->getModuleInst();
+    for (IRInst* child : moduleInst->getChildren())
+    {
+        // If we find a function add it to the list
+        if (auto funcInst = as<IRFunc>(child))
+        {
+            ioFuncs.add(funcInst);
+        }
+    }
+}
+
+
 void LivenessContext::_maybeAddEndAtBlockStart(BlockIndex blockIndex)
 {
     auto block = _getBlock(blockIndex);
@@ -972,9 +1009,9 @@ void LivenessContext::_findInstRunsForBlocks()
     }
 }
 
-void LivenessContext::_processRoot(const Location* locations, Count locationsCount)
+void LivenessContext::_processRoot(IRLiveRangeStart* const* rangeStarts, Count rangeStartsCount)
 {
-    if (locationsCount <= 0)
+    if (rangeStartsCount <= 0)
     {
         return;
     }
@@ -986,28 +1023,21 @@ void LivenessContext::_processRoot(const Location* locations, Count locationsCou
     }
     m_instRuns.clear();
     
-    auto root = locations[0].root;
+    auto root = rangeStarts[0]->getReferenced();
 
     // Set the root
     m_root = root;
     m_rootBlock = as<IRBlock>(m_root->parent);
 
     // Add all the live starts
-    m_liveRangeStarts.setCount(locationsCount);
-    for (Index i = 0; i < locationsCount; ++i)
+    for (Index i = 0; i < rangeStartsCount; ++i)
     {
-        const auto& location = locations[i];
-        SLANG_ASSERT(location.root == root);
+        auto rangeStart = rangeStarts[i];
 
-        // Add the start location
-        m_builder.setInsertLoc(location.startLocation);
-        // Emit the range start
-        auto liveStart = m_builder.emitLiveRangeStart(location.root);
+        // Check it references the same root
+        SLANG_ASSERT(rangeStart->getReferenced() == root);
 
-        // Save the start
-        m_liveRangeStarts[i] = liveStart;
-
-        _addStartInst(liveStart);
+        _addStartInst(rangeStart);
     }
 
     // Find all of the aliases and access to this root
@@ -1017,10 +1047,10 @@ void LivenessContext::_processRoot(const Location* locations, Count locationsCou
     _findInstRunsForBlocks();
 
     // Now we want to find all of the ends for each start
-    for (auto liveStart : m_liveRangeStarts)
+    for (Index i = 0; i < rangeStartsCount; ++i)
     {
         // We want to process this RangeStart for the root, to find all of the ends
-        _findAndEmitRangeEnd(liveStart);
+        _findAndEmitRangeEnd(rangeStarts[i]);
     }
 
     // No root is active in processing
@@ -1028,16 +1058,10 @@ void LivenessContext::_processRoot(const Location* locations, Count locationsCou
     m_rootBlock = nullptr;
 }
 
-void LivenessContext::_processLocationsInFunction(const Location* locations, Count count)
+void LivenessContext::_processFunction(IRFunc* func)
 {
-    if (count <= 0)
-    {
-        return;
-    }
-    
-    const auto func = locations[0].function;
-    SLANG_UNUSED(func);
-    
+    SLANG_ASSERT(m_rangeStarts.getCount() > 0);
+
     // Create the dominator tree, for the function
     m_dominatorTree = computeDominatorTree(func);
 
@@ -1098,55 +1122,54 @@ void LivenessContext::_processLocationsInFunction(const Location* locations, Cou
     }
 
     // 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);
+        Index start = 0;
+        const Count count = m_rangeStarts.getCount();
+        while (start < count)
+        {
+            // 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);
 
-        // Process the root 
-        _processRoot(locations + start, end - start);       
+            // Process the root 
+            _processRoot(m_rangeStarts.getBuffer() + start, end - start);       
 
-        // Set start to the beginning of the next run
-        start = end;
+            // Set start to the beginning of the next run
+            start = end;
+        }
     }
 }
 
-void LivenessContext::processLocations(const List<Location>& inLocations)
+void LivenessContext::process()
 {
-    // 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();
+    // Find all of the funcs in the module
+    List<IRFunc*> funcs;
+    _findFuncs(m_module, funcs);
 
-    Index start = 0;
-    while (start < locationCount)
+    for (auto func : funcs)
     {
-        auto func = locations[start].function;
-        Index end = start + 1;
-
-        for (;end < locationCount && locations[end].function == func; ++end);
+        if (func->getFirstBlock() != nullptr)
+        {
+            m_rangeStarts.clear();
+            _findLiveStarts(func, m_rangeStarts);
 
-        // All of the locations from [start, end) are in the same function. Lets process all in one go...
-        _processLocationsInFunction(locations.getBuffer() + start, end - start);
+            if (m_rangeStarts.getCount() > 0)
+            {
+                // Sort into referenced/root start
+                m_rangeStarts.sort([&](IRLiveRangeStart* a, IRLiveRangeStart* b) -> bool { return a->getReferenced() < b->getReferenced(); });
 
-        // Look for next run
-        start = end;
+                _processFunction(func);
+            }
+        }
     }
 }
 
 } // anonymous
 
-static void _processFunction(IRFunc* funcInst, List<LivenessLocation>& ioLocations)
+static void _processFunction(IRFunc* funcInst, List<IRVar*>& ioVars)
 {
     // If it has no body, then we are done
     if (funcInst->getFirstBlock() == nullptr)
@@ -1162,42 +1185,60 @@ static void _processFunction(IRFunc* funcInst, List<LivenessLocation>& ioLocatio
             // We look for var declarations.
             if (auto varInst = as<IRVar>(inst))
             {
-                LivenessLocation location;
-
-                location.function = funcInst;
-                // Set the livness start to be after the var
-                location.startLocation = IRInsertLoc::after(varInst);
-                location.root = varInst;
+                ioVars.add(varInst);
 
-                ioLocations.add(location);
             }
         }
     }
 }
 
-/* static */void LivenessUtil::locateVariables(IRModule* module, List<Location>& ioLocations)
+/* static */void LivenessUtil::addVariableRangeStarts(IRModule* module, LivenessMode livenessMode)
 {
+    if (!isEnabled(livenessMode))
+    {
+        return;
+    }
+
     // When we process liveness, is prior to output for a target
     // So post specialization
 
-    IRModuleInst* moduleInst = module->getModuleInst();
+    SharedIRBuilder sharedBuilder;
+    IRBuilder builder;
 
-    for (IRInst* child : moduleInst->getChildren())
+    sharedBuilder.init(module);
+    builder.init(sharedBuilder);
+
+    // Storage for found vars
+    List<IRVar*> vars;
+
+    List<IRFunc*> funcs;
+    _findFuncs(module, funcs);
+
+    for (auto func : funcs)
     {
-        // We want to find all of the functions, and process them
-        if (auto funcInst = as<IRFunc>(child))
+        // Clear as we will reuse the vars storage
+        vars.clear();
+
+        // Find all the vars in the function
+        _processFunction(func, vars);
+
+        for (auto var : vars)
         {
-            // Then we want to look through their definition
-            // inserting instructions that mark the liveness start/end
-            _processFunction(funcInst, ioLocations);
+            // Set liveness after the variable is declared
+            builder.setInsertLoc(IRInsertLoc::after(var));
+            // Emit a range start
+            builder.emitLiveRangeStart(var);
         }
     }
 }
 
-/* static */void LivenessUtil::addLivenessRanges(IRModule* module, const List<Location>& inLocations)
+/* static */void LivenessUtil::addRangeEnds(IRModule* module, LivenessMode livenessMode)
 {
-    LivenessContext context(module);
-    context.processLocations(inLocations);
+    if (isEnabled(livenessMode))
+    {
+        LivenessContext context(module, livenessMode);
+        context.process();
+    }
 }
 
 } // namespace Slang
diff --git a/source/slang/slang-ir-liveness.h b/source/slang/slang-ir-liveness.h
index 951af1793..db3c7633f 100644
--- a/source/slang/slang-ir-liveness.h
+++ b/source/slang/slang-ir-liveness.h
@@ -163,22 +163,25 @@ Similarly calling into a function could return a struct that contains fields whi
 fully specialized.
 */
 
-struct LivenessLocation
+/* The mode for liveness tracking. 
+
+Currently just controls enabling/disabling, but could be used to control other aspects. */
+enum class LivenessMode
 {
-	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
+	Disabled,
+	Enabled,
 };
 
+// Helper for testing if liveness is enabled.
+SLANG_FORCE_INLINE bool isEnabled(LivenessMode mode) { return mode != LivenessMode::Disabled; }
+
 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);
+		/// Locate all of the variables across the module and add live range starts.
+	static void addVariableRangeStarts(IRModule* module, LivenessMode mode);
 
-		/// 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);
+		/// Adds LiveRangeEnd instructions to demark the end of all of the liveness starts in the module
+	static void addRangeEnds(IRModule* module, LivenessMode mode);
 };
 
 }