diff options
| -rw-r--r-- | source/core/slang-uint-set.h | 8 | ||||
| -rw-r--r-- | source/slang/slang-capability.cpp | 172 | ||||
| -rw-r--r-- | source/slang/slang-capability.h | 11 | ||||
| -rw-r--r-- | tools/slang-capability-generator/capability-generator-main.cpp | 130 |
4 files changed, 145 insertions, 176 deletions
diff --git a/source/core/slang-uint-set.h b/source/core/slang-uint-set.h index 7e08500fd..077bc7981 100644 --- a/source/core/slang-uint-set.h +++ b/source/core/slang-uint-set.h @@ -19,8 +19,10 @@ constexpr Index intLog2(unsigned x) return x == 1 ? 0 : 1 + intLog2(x >> 1); } +// if `in` is 0, result is undefined behavior static inline Index bitscanForward(uint64_t in) { + SLANG_ASSERT(in != 0); #if defined(_MSC_VER) #ifdef _WIN64 @@ -28,14 +30,12 @@ static inline Index bitscanForward(uint64_t in) _BitScanForward64((unsigned long*)&out, in); return Index(out); #else - constexpr uint32_t bitsInType = sizeof(uint32_t) * 8; uint32_t out; // check for 0s in 0bit->31bit. If all 0's, check for 0s in 32bit->63bit - _BitScanForward((unsigned long*)&out, *(((uint32_t*)&in) + 1)); - if (out != bitsInType) + if (_BitScanForward((unsigned long*)&out, *(((uint32_t*)&in) + 1))) return Index(out); _BitScanForward((unsigned long*)&out, *(((uint32_t*)&in))); - return Index(out + bitsInType); + return Index(out); #endif// #ifdef _WIN64 #else diff --git a/source/slang/slang-capability.cpp b/source/slang/slang-capability.cpp index c717a0ab9..750026a64 100644 --- a/source/slang/slang-capability.cpp +++ b/source/slang/slang-capability.cpp @@ -60,24 +60,12 @@ struct CapabilityAtomInfo /// Ranking to use when deciding if this atom is a "better" one to select. uint32_t rank; - /// Canonical representation in the form of disjunction-of-conjunction of atoms. - ArrayView<ArrayView<CapabilityName>> canonicalRepresentation; + /// Canonical representation of atoms in the form of disjoint conjunctions of atoms. + ArrayView<CapabilityAtomSet*> canonicalRepresentation; }; #include "slang-generated-capability-defs-impl.h" -static UInt asAtomUInt(CapabilityName name) -{ - SLANG_ASSERT((CapabilityAtom)name < CapabilityAtom::Count); - return (UInt)((CapabilityAtom)name); -} - -static CapabilityAtom asAtom(CapabilityName name) -{ - SLANG_ASSERT((CapabilityAtom)name < CapabilityAtom::Count); - return (CapabilityAtom)name; -} - /// Get the extended information structure for the given capability `atom` static CapabilityAtomInfo const& _getInfo(CapabilityName atom) { @@ -170,9 +158,8 @@ bool isCapabilityDerivedFrom(CapabilityAtom atom, CapabilityAtom base) const auto& info = kCapabilityNameInfos[Index(atom)]; for (auto cur : info.canonicalRepresentation) { - for (auto cbase : cur) - if (asAtom(cbase) == base) - return true; + if (cur->contains((UInt)base)) + return true; } return false; @@ -180,111 +167,89 @@ bool isCapabilityDerivedFrom(CapabilityAtom atom, CapabilityAtom base) //// CapabiltySet -void CapabilitySet::addToTargetCapabilityWithValidUIntSetAndTargetAndStage(CapabilityName target, CapabilityName stage, CapabilityAtomSet setToAdd) +CapabilityAtom getTargetAtomInSet(const CapabilityAtomSet& atomSet) { - SLANG_ASSERT(target != CapabilityName::Invalid && stage != CapabilityName::Invalid); - auto stageAtom = asAtom(stage); - auto targetAtom = asAtom(target); - CapabilityTargetSet& targetSet = m_targetSets[targetAtom]; - targetSet.target = targetAtom; - targetSet.shaderStageSets.reserve(kCapabilityStageCount); - - auto& localStageSets = targetSet.shaderStageSets[stageAtom]; - localStageSets.stage = stageAtom; + auto targetSet = getAtomSetOfTargets(); + CapabilityAtomSet out; + CapabilityAtomSet::calcIntersection(out, targetSet, atomSet); + auto iter = out.begin(); + if (iter == out.end()) + return CapabilityAtom::Invalid; + return (CapabilityAtom)*iter; +} - localStageSets.addNewSet(std::move(setToAdd)); +CapabilityAtom getStageAtomInSet(const CapabilityAtomSet& atomSet) +{ + auto stageSet = getAtomSetOfStages(); + CapabilityAtomSet out; + CapabilityAtomSet::calcIntersection(out, stageSet, atomSet); + auto iter = out.begin(); + if (iter == out.end()) + return CapabilityAtom::Invalid; + return (CapabilityAtom)*iter; } -void CapabilitySet::addToTargetCapabilityWithTargetAndStageAtom(CapabilityName target, CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation) +template<CapabilityName keyholeAtomToPermuteWith> +void CapabilitySet::addPermutationsOfConjunctionForEachInContainer(CapabilityAtomSet& setToPermutate, const CapabilityAtomSet& elementsToPermutateWith, CapabilityAtom knownTargetAtom, CapabilityAtom knownStageAtom) { - // If no provided 'stage', set the capability as a target of all stages - if (stage == CapabilityName::Invalid) + for(auto i : elementsToPermutateWith) { - auto info = _getInfo(CapabilityName::any_stage); - List<CapabilityName> newArr; - auto count = canonicalRepresentation.getCount(); - newArr.setCount(count + 1); - memcpy(newArr.getBuffer(), canonicalRepresentation.getBuffer(), count * sizeof(CapabilityName)); - m_targetSets[asAtom(target)].shaderStageSets.reserve(info.canonicalRepresentation.getCount()); - for (auto i : info.canonicalRepresentation) + CapabilityName atom = (CapabilityName)i; + CapabilityAtomSet conjunctionPermutation = setToPermutate; + auto targetInfo = _getInfo(atom); + conjunctionPermutation.add(*targetInfo.canonicalRepresentation[0]); + + if constexpr (keyholeAtomToPermuteWith == CapabilityName::target) { - newArr[count] = i[0]; - addToTargetCapabilityWithTargetAndStageAtom(target, i[0], newArr.getArrayView()); + addConjunction(conjunctionPermutation, (CapabilityAtom)atom, knownStageAtom); + } + else if constexpr (keyholeAtomToPermuteWith == CapabilityName::stage) + { + addConjunction(conjunctionPermutation, knownTargetAtom, (CapabilityAtom)atom); + } + else + { + addConjunction(conjunctionPermutation, knownTargetAtom, knownStageAtom); } - return; } - - CapabilityAtomSet setToAdd = CapabilityAtomSet((UInt)CapabilityAtom::Count); - for(auto i : canonicalRepresentation) - setToAdd.add(asAtomUInt(i)); - - addToTargetCapabilityWithValidUIntSetAndTargetAndStage(target, stage, setToAdd); } -// No targets atoms have been defined on yet, set stage to target any_target capability -void CapabilitySet::addToTargetCapabilityWithStageAtom(CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation) +void CapabilitySet::addConjunction(CapabilityAtomSet conjunction, CapabilityAtom knownTargetAtom, CapabilityAtom knownStageAtom) { - - if (m_targetSets.getCount() == 0) + if (knownTargetAtom == CapabilityAtom::Invalid) { - const auto anyTargetInfo = _getInfo(CapabilityName::any_target); - CapabilityAtomSet setToAdd; - setToAdd.resize((UInt)CapabilityAtom::Count); - for (int i = 0; i < canonicalRepresentation.getCount(); i++) - setToAdd.add((UInt)canonicalRepresentation[i]); - CapabilityName targetAtom{}; - for (const auto& targetAtomCanonicalRep : anyTargetInfo.canonicalRepresentation) + knownTargetAtom = getTargetAtomInSet(conjunction); + // if no target in conjunction, add a permutation of the conjunction with every target + if (knownTargetAtom == CapabilityAtom::Invalid) { - for (auto anyTargetAtom : targetAtomCanonicalRep) - { - setToAdd.add((UInt)anyTargetAtom); - if (_getInfo(anyTargetAtom).abstractBase == CapabilityName::target) - targetAtom = anyTargetAtom; - } - addToTargetCapabilityWithValidUIntSetAndTargetAndStage(targetAtom, stage, setToAdd); - for (auto anyTargetAtom : targetAtomCanonicalRep) - setToAdd.remove((UInt)anyTargetAtom); + addPermutationsOfConjunctionForEachInContainer<CapabilityName::target>(conjunction, getAtomSetOfTargets(), CapabilityAtom::Invalid, getStageAtomInSet(conjunction)); + return; } } -} - -void CapabilitySet::addToTargetCapabilityWithTargetAndOrStageAtom(CapabilityName target, CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation) -{ - if(target != CapabilityName::Invalid) - addToTargetCapabilityWithTargetAndStageAtom(target, stage, canonicalRepresentation); - else if(stage != CapabilityName::Invalid) - addToTargetCapabilityWithStageAtom(stage, canonicalRepresentation); -} + auto& capabilitySetToTargetSet = m_targetSets[knownTargetAtom]; + capabilitySetToTargetSet.target = knownTargetAtom; -void CapabilitySet::addToTargetCapabilitesWithCanonicalRepresentation(const ArrayView<CapabilityName>& canonicalRepresentation) -{ - // only need to search i == 0/1 to find a relevant node - // target node should ALWAYS be first, so if we find a node, we stop searching. This is the most important node. We assume only stage+target with this logic. - // canonicalRepresentation of node has optionally 0-1 abstract node of each type, with a minimum of 1 abstract node total. - CapabilityName target = CapabilityName::Invalid; - CapabilityName stage = CapabilityName::Invalid; - for (const auto& i : canonicalRepresentation) + if (knownStageAtom == CapabilityAtom::Invalid) { - const auto info = _getInfo(i); - if (info.abstractBase == CapabilityName::Invalid) - continue; - else if (info.abstractBase == CapabilityName::target) - target = i; - else if (info.abstractBase == CapabilityName::stage) - stage = i; - - if (target != CapabilityName::Invalid && stage != CapabilityName::Invalid) - break; + knownStageAtom = getStageAtomInSet(conjunction); + // if no target in conjunction, add a permutation of the conjunction with every stage + if (knownStageAtom == CapabilityAtom::Invalid) + { + capabilitySetToTargetSet.shaderStageSets.reserve(kCapabilityStageCount); + addPermutationsOfConjunctionForEachInContainer<CapabilityName::stage>(conjunction, getAtomSetOfStages(), knownTargetAtom, CapabilityAtom::Invalid); + return; + } } - - addToTargetCapabilityWithTargetAndOrStageAtom(target, stage, canonicalRepresentation); + auto& targetSetToStageSet = capabilitySetToTargetSet.shaderStageSets[knownStageAtom]; + targetSetToStageSet.stage = knownStageAtom; + targetSetToStageSet.addNewSet(std::move(conjunction)); } void CapabilitySet::addUnexpandedCapabilites(CapabilityName atom) { auto info = _getInfo(atom); - for (const auto& cr : info.canonicalRepresentation) - addToTargetCapabilitesWithCanonicalRepresentation(cr); + for (const auto cr : info.canonicalRepresentation) + addConjunction(*cr, CapabilityAtom::Invalid, CapabilityAtom::Invalid); } CapabilitySet::CapabilitySet() @@ -506,12 +471,6 @@ void CapabilitySet::nonDestructiveJoin(const CapabilitySet& other) } } -void CapabilitySet::addCapability(List<List<CapabilityAtom>>& atomLists) -{ - for (const auto& cr : atomLists) - addToTargetCapabilitesWithCanonicalRepresentation( (*(List<CapabilityName>*)(&cr)).getArrayView()); -} - CapabilitySet CapabilitySet::getTargetsThisHasButOtherDoesNot(const CapabilitySet& other) { CapabilitySet newSet{}; @@ -520,10 +479,7 @@ CapabilitySet CapabilitySet::getTargetsThisHasButOtherDoesNot(const CapabilitySe if (other.m_targetSets.tryGetValue(i.first)) continue; - newSet.m_targetSets[i.first].target = i.first; - auto info = _getInfo(i.first); - if(info.canonicalRepresentation.getCount() > 0) - newSet.addToTargetCapabilityWithTargetAndStageAtom((CapabilityName)i.first, CapabilityName::Invalid, info.canonicalRepresentation[0]); + newSet.m_targetSets[i.first] = this->m_targetSets[i.first]; } return newSet; } diff --git a/source/slang/slang-capability.h b/source/slang/slang-capability.h index 5ee79670b..6e123a9a6 100644 --- a/source/slang/slang-capability.h +++ b/source/slang/slang-capability.h @@ -173,11 +173,12 @@ public: /// Find any capability sets which are in 'available' but not in 'required'. Return false if this situation occurs. static bool checkCapabilityRequirement(CapabilitySet const& available, CapabilitySet const& required, CapabilityAtomSet& outFailedAvailableSet); - inline void addToTargetCapabilityWithValidUIntSetAndTargetAndStage(CapabilityName target, CapabilityName stage, CapabilityAtomSet setToAdd); - inline void addToTargetCapabilityWithTargetAndStageAtom(CapabilityName target, CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation); - inline void addToTargetCapabilityWithTargetAndOrStageAtom(CapabilityName target, CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation); - inline void addToTargetCapabilityWithStageAtom(CapabilityName stage, const ArrayView<CapabilityName>& canonicalRepresentation); - inline void addToTargetCapabilitesWithCanonicalRepresentation(const ArrayView<CapabilityName>& atom); + // For each element in `elementsToPermutateWith`, create and add a different conjunction permutation by adding to `setToPermutate`. + template<CapabilityName keyholeAtomToPermuteWith> + void addPermutationsOfConjunctionForEachInContainer(CapabilityAtomSet& setToPermutate, const CapabilityAtomSet& elementsToPermutateWith, CapabilityAtom knownTargetAtom, CapabilityAtom knownStageAtom); + // This is used for adding conjunctions directly and efficently, this is not functionally a join. + // if `knownStage`/`knownTarget` is not CapabilityAtom::Invalid, the given atom will be assumed as an assigned key atom (faster) + inline void addConjunction(CapabilityAtomSet conjunction, CapabilityAtom knownTarget, CapabilityAtom knownStage); inline void addUnexpandedCapabilites(CapabilityName atom); CapabilityTargetSets& getCapabilityTargetSets() { return m_targetSets; } diff --git a/tools/slang-capability-generator/capability-generator-main.cpp b/tools/slang-capability-generator/capability-generator-main.cpp index e31822e05..b08496e35 100644 --- a/tools/slang-capability-generator/capability-generator-main.cpp +++ b/tools/slang-capability-generator/capability-generator-main.cpp @@ -657,22 +657,36 @@ void calcCanonicalRepresentations(DiagnosticSink* sink, List<RefPtr<CapabilityDe calcCanonicalRepresentation(sink, def, mapEnumValueToDef); } -void outputUIntSetAsBufferValues(const String& nameOfBuffer, StringBuilder& resultBuilder, UIntSet& set) +// Create a local UIntSet with data +void outputLocalUIntSetBuffer(const String& nameOfBuffer, StringBuilder& resultBuilder, UIntSet& set) { - // store UIntSet::Element as uint8_t to stay sizeof(UIntSet::Element) independent. - // underlying type may change, bits stay the same. - resultBuilder << "inline static CapabilityAtomSet generate_" << nameOfBuffer << "()\n"; - resultBuilder << "{\n"; - resultBuilder << " CapabilityAtomSet generatedSet;\n"; - + resultBuilder << " CapabilityAtomSet " << nameOfBuffer << ";\n"; + resultBuilder << " " << nameOfBuffer << ".resizeBackingBufferDirectly(" << set.getBuffer().getCount() << ");\n"; for (Index i = 0; i < set.getBuffer().getCount(); i++) { - resultBuilder << " generatedSet.addRawElement(UIntSet::Element(" << set.getBuffer()[i] << "UL), " << i << ");\n"; + resultBuilder << " " << nameOfBuffer << ".addRawElement(UIntSet::Element(" << set.getBuffer()[i] << "UL), " << i << "); \n"; } - resultBuilder << " return generatedSet;\n"; +} + +// Create function to generate a UIntSet with initial data +void outputUIntSetGenerator(const String& nameOfGenerator, StringBuilder & resultBuilder, UIntSet & set) +{ + resultBuilder << "inline static CapabilityAtomSet " << nameOfGenerator << "()\n"; + resultBuilder << "{\n"; + auto nameOfBackingData = nameOfGenerator + "_data"; + outputLocalUIntSetBuffer(nameOfBackingData, resultBuilder, set); + resultBuilder << " return " << nameOfBackingData << ";\n"; resultBuilder << "}\n"; +} - resultBuilder << "const static CapabilityAtomSet " << nameOfBuffer << " = generate_" << nameOfBuffer << "();\n"; + +UIntSet atomSetToUIntSet(const List<CapabilityDef*>& atomSet) +{ + UIntSet set{}; + // Last element is generally a larger number. Start from there to minimize reallocations. + for (Index i = atomSet.getCount()-1; i >= 0; i--) + set.add(atomSet[i]->enumValue); + return set; } SlangResult generateDefinitions(DiagnosticSink* sink, List<RefPtr<CapabilityDef>>& defs, StringBuilder& sbHeader, StringBuilder& sbCpp) @@ -755,50 +769,56 @@ SlangResult generateDefinitions(DiagnosticSink* sink, List<RefPtr<CapabilityDef> anyStageAtomSet.add(def->enumValue); } } - outputUIntSetAsBufferValues("kAnyTargetUIntSetBuffer", anyTargetUIntSetHash, anyTargetAtomSet); - outputUIntSetAsBufferValues("kAnyStageUIntSetBuffer", anyStageUIntSetHash, anyStageAtomSet); - + outputUIntSetGenerator("generatorOf_kAnyTargetUIntSetBuffer", anyTargetUIntSetHash, anyTargetAtomSet); + anyTargetUIntSetHash << "const static CapabilityAtomSet kAnyTargetUIntSetBuffer = generatorOf_kAnyTargetUIntSetBuffer();\n"; + sbCpp << anyTargetUIntSetHash; + + outputUIntSetGenerator("generatorOf_kAnyStageUIntSetBuffer", anyStageUIntSetHash, anyStageAtomSet); + anyStageUIntSetHash << "const static CapabilityAtomSet kAnyStageUIntSetBuffer = generatorOf_kAnyStageUIntSetBuffer();\n"; + sbCpp << anyStageUIntSetHash; + sbHeader << "\nenum {\n"; sbHeader << " kCapabilityTargetCount = " << targetCount << ",\n"; sbHeader << " kCapabilityStageCount = " << stageCount << ",\n"; sbHeader << "};\n\n"; calcCanonicalRepresentations(sink, defs, mapEnumValueToDef); - List<String> capabiltiyNameArray; - List<SerializedArrayView> serializedCapabilityArrays; - List<SerializedArrayView> serializedAtomDisjunctions; - auto serializeConjunction = [&](const List<CapabilityDef*>& capabilities) -> SerializedArrayView + struct SerializedConjunction + { + SerializedConjunction() + { + } + SerializedConjunction(const String& initFunctionName, UIntSet& data) : + m_initFunctionName(initFunctionName), m_data(data) + { + } + String m_initFunctionName; + UIntSet m_data; + }; + List<SerializedConjunction> serializedCapabilitesCache; + + List<Index> serializedAtomDisjunctions; + auto serializeConjunction = [&](const List<CapabilityDef*>& capabilities, CapabilityDef* parentDef, Index conjunctionNumber) -> Index { + auto capabilitiesAsUIntSet = atomSetToUIntSet(capabilities); // Do we already have a serialized capability array that is the same the one we are trying to serialize? - for (auto existingArray : serializedCapabilityArrays) + for (Index i = 0; i < serializedCapabilitesCache.getCount(); i++) { - if (existingArray.count == capabilities.getCount()) + auto& existingSet = serializedCapabilitesCache[i].m_data; + if (existingSet == capabilitiesAsUIntSet) { - bool match = true; - for (Index i = 0; i < capabilities.getCount(); i++) - { - if (capabiltiyNameArray[existingArray.first+i] != capabilities[i]->name) - { - match = false; - break; - } - } - if (match) - return existingArray; + return i; } } - SerializedArrayView result; - result.first = capabiltiyNameArray.getCount(); - for (auto capability : capabilities) - { - capabiltiyNameArray.add(capability->name); - } - result.count = capabilities.getCount(); - serializedCapabilityArrays.add(result); + auto initName = "generatorOf_" + parentDef->name + "_conjunction"+String(conjunctionNumber); + outputUIntSetGenerator(initName, sbCpp, capabilitiesAsUIntSet); + + auto result = serializedCapabilitesCache.getCount(); + serializedCapabilitesCache.add(SerializedConjunction(initName + "()", capabilitiesAsUIntSet)); return result; }; - auto serializeDisjunction = [&](const List<SerializedArrayView>& conjunctions) -> SerializedArrayView + auto serializeDisjunction = [&](const List<Index>& conjunctions) -> SerializedArrayView { SerializedArrayView result; result.first = serializedAtomDisjunctions.getCount(); @@ -811,35 +831,23 @@ SlangResult generateDefinitions(DiagnosticSink* sink, List<RefPtr<CapabilityDef> }; for (auto def : defs) { - List<SerializedArrayView> conjunctions; + List<Index> conjunctions; for (auto& c : def->canonicalRepresentation) - conjunctions.add(serializeConjunction(c)); + conjunctions.add(serializeConjunction(c, def, conjunctions.getCount())); def->serializedCanonicalRepresentation = serializeDisjunction(conjunctions); } - sbCpp << anyTargetUIntSetHash; - sbCpp << anyStageUIntSetHash; - - sbCpp << "static CapabilityName kCapabilityArray[] = {\n"; + sbCpp << "static CapabilityAtomSet kCapabilityArray[] = {\n"; Index arrayIndex = 0; - sbCpp << " /* [0] @0: */ "; - for (Index i = 0; i < capabiltiyNameArray.getCount(); ++i) + for (Index i = 0; i < serializedCapabilitesCache.getCount(); ++i) { - sbCpp << " CapabilityName::" << capabiltiyNameArray[i] << ","; - if (i + 1 == serializedCapabilityArrays[arrayIndex].first + serializedCapabilityArrays[arrayIndex].count) - { - arrayIndex++; - if (arrayIndex == serializedCapabilityArrays.getCount()) - sbCpp << "\n"; - else - sbCpp << "\n /* [" << arrayIndex << "] @" << serializedCapabilityArrays[arrayIndex].first <<": */ "; - } + sbCpp << " " << serializedCapabilitesCache[i].m_initFunctionName << ",\n"; } sbCpp << "};\n"; - sbCpp << "static ArrayView<CapabilityName> kCapabilityConjunctions[] = {\n"; + sbCpp << "static CapabilityAtomSet* kCapabilityConjunctions[] = {\n"; for (auto c : serializedAtomDisjunctions) { - sbCpp << " { kCapabilityArray + " << c.first << ", " << c.count << " },\n"; + sbCpp << " kCapabilityArray + " << c << ", \n"; } sbCpp << "};\n"; @@ -882,8 +890,12 @@ SlangResult generateDefinitions(DiagnosticSink* sink, List<RefPtr<CapabilityDef> } sbCpp << ", "; + // rank + sbCpp << def->rank; + sbCpp << ", "; + // canonnical representation. - sbCpp << def->rank << ", { kCapabilityConjunctions + " << def->serializedCanonicalRepresentation.first << ", " << def->serializedCanonicalRepresentation.count << "} },\n"; + sbCpp << "{ kCapabilityConjunctions + " << def->serializedCanonicalRepresentation.first << ", " << def->serializedCanonicalRepresentation.count << "} },\n"; } sbCpp << "};\n"; |