Add first steps toward a "capability" system (#1636)

* Add first steps toward a "capability" system

We already have cases in the stdlib where we mark declarations as being specific to certain targets, e.g.:

```
// My ordinary function to add two numbers.
// Works everywhere.
//
void myFunc(int a, int b) { return a + b; }

// On the "coolgpu" target, we can use a secret intrinsic
// that adds numbers even faster!
//
__specialized_for_target(coolgpu)
void myFunc(int a, int b) { return __secretIntrinsic(a, b); }
```

The existing logic for dealing with these modifiers (`__specialized_for_target` and `__target_intrinsic`) was almost entirely string-based. We would turn the chosen compilation target into a string, and then use that to try and search for the "best" definition of a function at a few steps:

* During IR linking, we always pick one definition of an `[import]`ed function, and that definition will be the one with the "best" target-specialization modifier (if any)

* During final code generation, we always look up the "best" target-intrinsic modifier, and use it as the template for the code we output.

This change preserves the basic flow there, but replaces the ad hoc string-based logic with something a bit more principled, in terms of a new `CapabilitySet` type.

A `CapabilitySet` represents a set of zero or more atomic features (here represented as `CapabilityAtom`s). What a `CapabilitySet` means depends on how and where it is used:

* A compilation target implies a `CapabilitySet` where the contents of the set are the features the target *supports*.

* A `CapabilitySet` attached to a declaration (or a modifier on that declaration) describes a set of feature that declaration *requires*.

The current implementation of `CapabilitySet` is wasteful and inefficient, but that is something we can iterate on over time.

In practice, most of the current code only ever uses capability sets that are either empty (because they represent a function with no specific requirements) or singleton (because they represent asingle atomic capability like "is a GLSL target," "is an HLSL target," etc.).

The main goal here was to put in the skeleton of a new system, including some of the features it might need down the line, and then to leave changes that eventually use the greater flexibility for later. Eventually, the capability system should encompass:

* Differences between shader model versions, GLSL versions, SPIR-V versions, etc. (currently tracked with other modifiers)

* Optional extensions, and functions that are made available only with certain extensions (currently tracked with other modifiers)

* Front-end checking that the call graph of a program doesn't violate any capability-requirements (e.g., having a GLSL+HLSL portable function call a GLSL-only subroutine)

* Hypothetically we can also try to fold stage-specific (vertex-only, fragment-only, etc.) functions into this system, but doing so would require more linker cleverness if we allow overloading on stages (since we might have to clone a caller if it calls through to a callee with multiple stage-specific versions)

One important complication that the system has to deal with just because of the "do what I mean" nature of the current compiler is that somethings a current Slang user might compile for target X and specify version N, but then use a function that actually requires version N+1 of that target. Currently the Slang compiler silently "upgrades" the version(s) used by user code in these cases, because it is often what users want in cross-compilation scenarios.

Dealing with the "silent upgrade" situation requires us to be a little careful and sometimes pick a "best" capability set that doesn't appear to be supported on our target. Refining that system and potentially getting rid of the "do what I mean" behavior over time could be a goal for future changes.

* fixup: handle case where value is incompatible during linking

1 files changed, 428 insertions, 0 deletions

diff --git a/source/slang/slang-capability.cpp b/source/slang/slang-capability.cpp
new file mode 100644
index 000000000..7b4361a58
--- /dev/null
+++ b/source/slang/slang-capability.cpp
@@ -0,0 +1,428 @@
+// slang-capability.cpp
+#include "slang-capability.h"
+
+// This file implements the core of the "capability" system.
+
+namespace Slang
+{
+
+//
+// CapabilityAtom
+//
+
+// We are going to divide capabilities into a few categories,
+// which will be represented as flags for now.
+//
+// Every capability will be either concrete or abstract.
+// An abstract capability basically represents a category
+// of related capabilities that all fill a similar role.
+// For example, we could have an abstract capability that
+// represents "stages" and then the concrete capabilities
+// `vertex`, `fragment`, etc. would inherit from it.
+//
+// Abstract capabilities are critical in our model for
+// knowing when two capabilities are fundamentally incompatible.
+// For example, it is meaningless to compile code for both
+// the `vertex` and `fragment` capabilities at the same time,
+// because no target processor supports both at once.
+//
+// TODO: It is possible that instead of flags this could simply
+// identify a "kind" of atom, with two different states.
+//
+// TODO: It is likely that in a future change we will want to
+// add a third case here for "alias" capabilities, which are
+// pseudo-atomic capabilities that are just equivalent to
+// the set of their bases.
+//
+typedef uint32_t CapabilityAtomFlags;
+enum : CapabilityAtomFlags
+{
+    kCapabilityAtomFlags_Concrete = 0,
+    kCapabilityAtomFlags_Abstract = 1 << 0,
+};
+
+// The macros in the `slang-capability-defs.h` file will be used
+// to fill out a `static const` array of information about each
+// capability atom.
+//
+struct CapabilityAtomInfo
+{
+        /// The API-/language-exposed name of the capability.
+    char const*         name;
+
+        /// Flags to determine if the capability is concrete-vs-abstract, etc.
+    CapabilityAtomFlags flags;
+    CapabilityAtom      bases[4];
+};
+//
+// The array is going to be sized to include an entry for `CapabilityAtom::Invalid`
+// which as a value of -1, so we need to size the array one larger than the `Count`
+// value.
+//
+static const CapabilityAtomInfo kCapabilityAtoms[Int(CapabilityAtom::Count) + 1] =
+{
+    { "invalid", 0, { CapabilityAtom::Invalid, CapabilityAtom::Invalid, CapabilityAtom::Invalid, CapabilityAtom::Invalid } },
+
+#define SLANG_CAPABILITY_ATOM(ENUMERATOR, NAME, FLAGS, BASE0, BASE1, BASE2, BASE3) \
+    { #NAME, kCapabilityAtomFlags_##FLAGS, { CapabilityAtom::BASE0, CapabilityAtom::BASE1, CapabilityAtom::BASE2, CapabilityAtom::BASE3 } },
+#include "slang-capability-defs.h"
+};
+
+    /// Get the extended information structure for the given capability `atom`
+static CapabilityAtomInfo const& _getInfo(CapabilityAtom atom)
+{
+    SLANG_ASSERT(Int(atom) < Int(CapabilityAtom::Count));
+    return kCapabilityAtoms[Int(atom) + 1];
+}
+
+// One capability set or capability atom A implies another set/atom B
+// if any target that supports all of the atoms in A must also support
+// all of those in B.
+
+    /// Does `thisAtom` imply `thatAtom`?
+static bool _implies(CapabilityAtom thisAtom, CapabilityAtom thatAtom)
+{
+    // When looking at atoms, the immediate easy case is when
+    // the two atoms are the same: an atomic capability always
+    // implies itself.
+    //
+    if(thisAtom == thatAtom)
+        return true;
+
+    // Otherwise, we want to look at the bases of `thisAtom`
+    // to see if any of them imply `thatAtom`, since `thisAtom`
+    // implies each of its bases.
+    //
+    auto& thisAtomInfo = _getInfo(thisAtom);
+    for( auto thisAtomBase : thisAtomInfo.bases )
+    {
+        // The lists of bases are currently using `Invalid` as
+        // a sentinel value to terminate them, so we need to
+        // bail out of the loop when we see the sentinel.
+        //
+        if(thisAtomBase == CapabilityAtom::Invalid)
+            break;
+
+        if(_implies(thisAtomBase, thatAtom))
+            return true;
+    }
+
+    return false;
+}
+
+    /// Does `base` have any abstract capabilities in common with `otherAtom`
+    ///
+    /// This subroutine is a helper for `_isIncompatible`.
+static bool _hasAbstractBaseInCommon(CapabilityAtom base, CapabilityAtom otherAtom)
+{
+    // First we check the case where `base` itself is an abstract
+    // capability atom.
+    //
+    auto& baseAtomInfo = _getInfo(base);
+    if(baseAtomInfo.flags & kCapabilityAtomFlags_Abstract)
+    {
+        // If `base` is abstract, and `otherAtom` implies `base`,
+        // then that means that `otherAtom` includes one or
+        // more atoms that inherit from `base`, and thus the
+        // two have an abstract base in common.
+        //
+        if( _implies(otherAtom, base) )
+            return true;
+    }
+
+    // If `base` itself has bases, then we want to check if any
+    // of *those* are abstract bases that overlap with `otherAtom`.
+    //
+    for( auto baseBase : baseAtomInfo.bases )
+    {
+        if(baseBase == CapabilityAtom::Invalid)
+            break;
+
+        if(_hasAbstractBaseInCommon(baseBase, otherAtom))
+            return true;
+    }
+
+    // If we didn't manage to find any overlaps, then we conclude
+    // that there are no shared abstract bases.
+    //
+    return false;
+}
+
+    /// Is `thisAtom` incompatible with `thatAtom` (such that no target could ever support both at once)
+static bool _isIncompatible(CapabilityAtom thisAtom, CapabilityAtom thatAtom)
+{
+    // If either atom implies the other, then they aren't incompatible.
+    //
+    // For example, if there is an atom representing `sm_5_1` that inherits
+    // from an atom representing `sm_5_0`, then clearly the two aren't
+    // in any way incompatible (a single target can support both).
+    //
+    if(_implies(thisAtom, thatAtom) || _implies(thatAtom, thisAtom))
+        return false;
+
+    // If the two atoms are not in an inheritance relationship, then one of
+    // a few cases can apply:
+    //
+    // * They have no common bases; in this case they are compatible.
+    //   An example would be `vertex` and `sm_5_0`.
+    //
+    // * They have a common base, but it is not marked abstract; in
+    //   this case they are compatible. E.g., two GLSL extensions that
+    //   both inherit from the `glsl` capability should not conflict.
+    //
+    // * They have a common base that is marked abstract; in this
+    //   case they are incompatible. An example would be `vertex`
+    //   and `fragment` both inheriting from the abstract atom
+    //   `__stage`.
+    //
+    // To summarize the above list, we note that two atoms are
+    // incompatible with they have an abstract base in common.
+    //
+    return _hasAbstractBaseInCommon(thisAtom, thatAtom);
+
+    // TODO: The above logic is a bit off, but in a way that doesn't
+    // matter just yet.
+    //
+    // We currently have capabilities like:
+    //
+    //      abstract capability __target;
+    //      capability hlsl : __target;
+    //      capability glsl : __target;
+    //
+    // In this case it is clear that `hlsl` and `glsl` should
+    // be incompatible, and that the rules as implemented
+    // make that the case.
+    //
+    // A problem arises when we start to add things like extensions:
+    //
+    //      capability EXT_cool_thing : glsl;
+    //      capability EXT_other_stuff : glsl;
+    //
+    // In this case, it also seems clear that `EXT_cool_thing`
+    // and `EXT_other_stuff` should be mutually compatible.
+    // However, with the rules implemented here right now, they
+    // would be found incompatible because they share the
+    // abstract base `__target`.
+    //
+    // In this specific case, we know that the relationship
+    // between the extensions is fine because they both inherit
+    // from `__target` *through* the concrete atom `glsl`.
+    //
+    // Before adding capabilities that represent optional
+    // extensions like this we need to codify the semantics
+    // for how incompatibility checks should work in terms
+    // of the inheritance graph of capability atoms.
+}
+
+CapabilityAtom findCapabilityAtom(UnownedStringSlice const& name)
+{
+    // For now we are implementing a linear search over the
+    // array of capability atoms to perform name lookup.
+    //
+    for( Index i = 0; i < Index(CapabilityAtom::Count); ++i )
+    {
+        // Note: using `_getInfo` here instead of accessing
+        // the `kCapabilityAtoms` array directly lets us
+        // avoid dealing with the offset-by-one indexing
+        // choice.
+        //
+        auto& capInfo = _getInfo(CapabilityAtom(i));
+        if(name == UnownedTerminatedStringSlice(capInfo.name))
+            return CapabilityAtom(i);
+    }
+    return CapabilityAtom::Invalid;
+}
+
+//
+// CapabilitySet
+//
+
+// The current design choice in `CapabilitySet` is that it blindly
+// stores exactly the atoms it is told to, without any up-front
+// processing.
+//
+// This choice has some down-sides, and there are other representations
+// that could be much nicer in the future. Possible improcements include:
+//
+// * The list of atoms could be *expanded* so that if it contains atom A
+//   and atom A implies atom B, then the list should also include B.
+//
+// * The list of atoms could be *minimized*, such that if atom A implies
+//   atom B, then any list that contains A does not include B (both
+//   expanded and minimized lists have different benefits).
+//
+// * The list of atoms could be deduplicated.
+//
+// * The list of atoms could be sorted.
+//
+// * The lists could be deduplicated and cached in some central place
+//   (the like the session) so that repreated attempts to create the
+//   same capability sets return the same objects.
+//
+// In some parts of the code below we will call out how these improvements
+// could affect the algorithms used.
+
+// Given our simple choices right now, the constructors for `CapabilitySet`
+// are all straightforward: just adding the right atoms to the list.
+
+CapabilitySet::CapabilitySet()
+{}
+
+CapabilitySet::CapabilitySet(Int atomCount, CapabilityAtom const* atoms)
+{
+    m_atoms.addRange(atoms, atomCount);
+}
+
+CapabilitySet::CapabilitySet(CapabilityAtom atom)
+{
+    m_atoms.add(atom);
+}
+
+CapabilitySet::CapabilitySet(List<CapabilityAtom> const& atoms)
+    : m_atoms(atoms)
+{}
+
+
+CapabilitySet CapabilitySet::makeEmpty()
+{
+    return CapabilitySet();
+}
+
+CapabilitySet CapabilitySet::makeInvalid()
+{
+    return CapabilitySet(CapabilityAtom::Invalid);
+}
+
+bool CapabilitySet::isEmpty() const
+{
+    // Checking if a capability set is empty is trivial in any representation;
+    // all we need to know is if it has zero atoms in its definition.
+    //
+    return m_atoms.getCount() == 0;
+}
+
+bool CapabilitySet::isInvalid() const
+{
+    // We will assume here that there is only one canonical representation of
+    // an invalid capability set, which is a singleton set of the `Invalid`
+    // atom.
+    //
+    // TODO: We should ensure that any algorithms that make new capability
+    // sets by combining others properly ensure that they return the
+    // canonical invalid set rather than any other set that happens to be
+    // invalid (e.g., a set {A,B} would be invalid if A and B are incompatible,
+    // but it would not be in the canonical form this subroutine checks).
+    //
+    if(m_atoms.getCount() != 1) return false;
+    return m_atoms[0] == CapabilityAtom::Invalid;
+}
+
+bool CapabilitySet::isIncompatibleWith(CapabilityAtom that) const
+{
+    // We know that capabilities that are in an inheritnace
+    // relationship with one another can't be incompatible.
+    //
+    if(this->implies(that) || CapabilitySet(that).implies(*this))
+        return false;
+
+    // Othwerise, we want to perform a check for each of the
+    // atoms in this set, whether it is incompatible with any
+    // of the atoms in the other set (which in this case is one atom).
+    //
+    for( auto thisAtom : this->m_atoms )
+    {
+        if(_isIncompatible(thisAtom, that))
+            return true;
+    }
+
+    return false;
+}
+
+bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const
+{
+    // We need to look at the atoms in `this` that are not
+    // present in `that`, and vice versa. For each such atom
+    // we will check if it is incompatible with the other, by
+    // virtue of the other already including a concrete atom
+    // that cannot co-exist with it.
+    //
+    for( auto thisAtom : this->m_atoms )
+    {
+        if(that.isIncompatibleWith(thisAtom))
+            return true;
+    }
+    for( auto thatAtom : that.m_atoms )
+    {
+        if(this->isIncompatibleWith(thatAtom))
+            return true;
+    }
+    return false;
+
+    // TODO: If we had a representation that stored a minified,
+    // sorted, deduplicated list of atoms, then it would be easy
+    // to iterate over the two lists in tandem and identify any
+    // element that is present in one list but not the other.
+    //
+    // Those elements would be the candidates that could cause
+    // incompatiblity, so that we wouldn't need to perform
+    // the check on each atom like we do above.
+}
+
+bool CapabilitySet::implies(CapabilitySet const& that) const
+{
+    // This capability set implies `other` if for every atom in `other`,
+    // that atom is present in this sets list of atoms or it is
+    // implies by something in the list of atoms.
+    //
+    for( auto atom : that.m_atoms )
+    {
+        if(!this->implies(atom))
+            return false;
+    }
+    return true;
+
+    // TODO: If we had a representation that stored an expanded
+    // sorted, deduplicated list of atoms, then we could
+    // check the `implies` relationship by scanning through
+    // the two lists in tandem and identifying any element
+    // in the `that` list that isn't in the `this` list.
+    // Such elements would indicate that `that` is not a subset
+    // of `this`.
+}
+
+
+bool CapabilitySet::implies(CapabilityAtom atom) const
+{
+    // If our list of explicit atoms contains `atom`, then
+    // we definitely imply it.
+    //
+    // TODO: If we stored our atom lists sorted, then
+    // this operation could be logarithmic rather than
+    // linear.
+    //
+    if(m_atoms.contains(atom))
+        return true;
+
+    // If any of our atoms implies `atom` then we
+    // also imply it.
+    //
+    // TODO: If we stored an expanded atom list, then
+    // this recursion could be skipped completely, since
+    // the containment check above would cover inheirtance
+    // relationships too.
+    //
+    for( auto thisAtom : m_atoms )
+    {
+        if(_implies(thisAtom, atom))
+            return true;
+    }
+
+    return false;
+}
+
+bool CapabilitySet::operator==(CapabilitySet const& other) const
+{
+    return this->implies(other) && other.implies(*this);
+}
+
+}