From 4c4826d47eeef4675daae4ae53ff76f4d5ebd84a Mon Sep 17 00:00:00 2001
From: Yong He <yonghe@outlook.com>
Date: Thu, 16 Feb 2023 13:55:32 -0800
Subject: Overhaul global inst deduplication and cpp/cuda backend. (#2654)

* Overhaul global inst deduplication and cpp/cuda backend.

* Update IR documentation.

---------

Co-authored-by: Yong He <yhe@nvidia.com>
---
 source/slang/slang-ir-deduplicate.cpp | 154 ++++++++++++++--------------------
 1 file changed, 61 insertions(+), 93 deletions(-)

(limited to 'source/slang/slang-ir-deduplicate.cpp')

diff --git a/source/slang/slang-ir-deduplicate.cpp b/source/slang/slang-ir-deduplicate.cpp
index 51a677627..74efc3cb3 100644
--- a/source/slang/slang-ir-deduplicate.cpp
+++ b/source/slang/slang-ir-deduplicate.cpp
@@ -2,116 +2,84 @@
 
 namespace Slang
 {
-    struct DeduplicateContext
+    void SharedIRBuilder::deduplicateAndRebuildGlobalNumberingMap()
     {
-        SharedIRBuilder* builder;
-        IRInst* addValue(IRInst* value)
-        {
-            if (!value) return nullptr;
-            if (as<IRType>(value))
-                return addTypeValue(value);
-            if (auto constValue = as<IRConstant>(value))
-                return addConstantValue(constValue);
-            return value;
-        }
-        IRInst* addConstantValue(IRConstant* value)
-        {
-            IRConstantKey key = { value };
-            value->setFullType((IRType*)addValue(value->getFullType()));
-            if (auto newValue = builder->getConstantMap().TryGetValue(key))
-                return *newValue;
-            builder->getConstantMap()[key] = value;
-            return value;
-        }
-        IRInst* addTypeValue(IRInst* value)
-        {
-            // Do not deduplicate struct or interface types.
-            switch (value->getOp())
-            {
-            case kIROp_StructType:
-            case kIROp_InterfaceType:
-                return value;
-            default:
-                break;
-            }
+    }
 
-            for (UInt i = 0; i < value->getOperandCount(); i++)
-            {
-                value->setOperand(i, addValue(value->getOperand(i)));
-            }
-            value->setFullType((IRType*)addValue(value->getFullType()));
-            IRInstKey key = { value };
-            if (auto newValue = builder->getGlobalValueNumberingMap().TryGetValue(key))
-                return *newValue;
-            builder->getGlobalValueNumberingMap()[key] = value;
-            return value;
-        }
-    };
-    void SharedIRBuilder::deduplicateAndRebuildGlobalNumberingMap()
+    void SharedIRBuilder::replaceGlobalInst(IRInst* oldInst, IRInst* newInst)
+    {
+        oldInst->replaceUsesWith(newInst);
+    }
+
+    void SharedIRBuilder::removeHoistableInstFromGlobalNumberingMap(IRInst* instToRemove)
     {
-        DeduplicateContext context;
-        context.builder = this;
-        m_constantMap.Clear();
-        m_globalValueNumberingMap.Clear();
-        List<IRInst*> instToRemove;
-        for (auto inst : m_module->getGlobalInsts())
+        HashSet<IRInst*> userWorkListSet;
+        List<IRInst*> userWorkList;
+        auto addToWorkList = [&](IRInst* i)
         {
-            if (auto constVal = as<IRConstant>(inst))
-            {
-                auto newConst = context.addConstantValue(constVal);
-                if (newConst != constVal)
-                {
-                    constVal->replaceUsesWith(newConst);
-                    instToRemove.add(constVal);
-                }
-            }
-        }
-        for (auto inst : m_module->getGlobalInsts())
+            if (userWorkListSet.Add(i))
+                userWorkList.add(i);
+        };
+        addToWorkList(instToRemove);
+        for (Index i = 0; i < userWorkList.getCount(); i++)
         {
-            if (as<IRType>(inst) || as<IRSpecialize>(inst))
+            auto inst = userWorkList[i];
+            if (getIROpInfo(inst->getOp()).isHoistable())
             {
-                auto newInst = context.addTypeValue(inst);
-                if (newInst != inst)
+                _removeGlobalNumberingEntry(inst);
+                for (auto use = inst->firstUse; use; use = use->nextUse)
                 {
-                    inst->replaceUsesWith(newInst);
-                    instToRemove.add(inst);
+                    addToWorkList(use->getUser());
                 }
             }
         }
-        for (auto inst : instToRemove)
-            inst->removeAndDeallocate();
     }
 
-    void SharedIRBuilder::replaceGlobalInst(IRInst* oldInst, IRInst* newInst)
+    void addHoistableInst(
+        IRBuilder* builder,
+        IRInst* inst);
+
+    void SharedIRBuilder::tryHoistInst(IRInst* inst)
     {
-        List<IRUse*> uses;
-        for (auto use = oldInst->firstUse; use; use = use->nextUse)
-        {
-            uses.add(use);
-        }
+        List<IRInst*> workList;
+        HashSet<IRInst*> workListSet;
+        workList.add(inst);
+        workListSet.Add(inst);
+        IRBuilder builder(inst->getModule());
 
-        bool shouldUpdateGlobalNumberedCache = false;
-        for (auto use : uses)
+        for (Index i = 0; i < workList.getCount(); i++)
         {
-            use->set(newInst);
-            // depending on the type of the user inst, we may need to rebuild and update the global
-            // numbering cache.
-            if (isGloballyNumberedInst(use->getUser()))
+            auto item = workList[i];
+
+            // Does inst no longer depend on anything defined locally?
+            // If so we should hoist it.
+            bool shouldHoist = false;
+            for (UInt a = 0; a < item->getOperandCount(); a++)
             {
-                shouldUpdateGlobalNumberedCache = true;
+                auto opParent = item->getOperand(a)->getParent();
+                if (opParent != item->getParent())
+                {
+                    shouldHoist = true;
+                    break;
+                }
             }
-        }
-        oldInst->removeAndDeallocate();
-        if (shouldUpdateGlobalNumberedCache)
-        {
-            deduplicateAndRebuildGlobalNumberingMap();
-        }
-    }
 
-    bool SharedIRBuilder::isGloballyNumberedInst(IRInst* inst)
-    {
-        if (!inst->getParent() || inst->getParent()->getOp() != kIROp_Module)
-            return false;
-        return m_globalValueNumberingMap.ContainsKey(IRInstKey{inst});
+            // Hoisting this inst 
+            if (shouldHoist)
+            {
+                item->removeFromParent();
+                addHoistableInst(&builder, item);
+
+                // Continue to consider all users for hoisting.
+                for (auto use = item->firstUse; use; use = use->nextUse)
+                {
+                    if (getIROpInfo(use->getUser()->getOp()).isHoistable())
+                    {
+                        if (workListSet.Add(use->getUser()))
+                            workList.add(use->getUser());
+                    }
+                }
+            }
+        }
     }
 }
-- 
cgit v1.2.3