From 4ab545bcd0716cc3f2da432a921c1f53fdce7925 Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Fri, 27 Oct 2017 11:22:11 -0700 Subject: Initial work on support code generation for generics with constraints (#233) This change includes a lot of infrastructure work, but the main point is to allow code like the following: ``` // define an interface interface Helper { float help(); } // define a generic function that uses the interface float test( T t ) { return t.help(); } // define a type that implements the interface struct A : Helper { float help() { return 1.0 } } // define an ordinary function that calls the // generic function with a concrete type: float doIt() { A a; return test(a); } ``` Getting this to generate valid code involves a lot of steps. This change includes the initial version of all of these steps, but leaves a lot of gaps where more complete implementation is required. The changes include: - Member lookup on types has been centralized, and now handles the case where the type we are looking for a member in is a generic parameter (e.g., given `t.help()` we can now look up `help` in `Helper` by knowing that `t` is a `T` and `T` conforms to `Helper`). - There is an obvious cleanup still to be done here where the same exact logic should be used to look up available "constructor" declarations inside a type when the type is used like a function. - Add a notion of subtype constraint "wittnesses" to the type system. When a generic is declared as taking `` it really takes two generic parameters: the type `T` and a proof that `T` conforms to `Helper`. The actual arguments to a generic will then include both the type argument and a suitable witness argument (both type-level values). - As it stands right now, a witness wraps a `DeclRef` to the declaration that represents the appropriate subtype relationship. So if we have `struct A : Helper`, that `: Helper` part turns into an `InheritanceDecl` member, and a reference to that member can serve as a witness to the fact that `A` conforms to `Helper`. - Make explicit generic application `G` synthesize the additional arguments that represent conformances required by the generic. - This does *not* yet deal with the case where a generic is implicitly specialized as part of an ordinary call `G(a,b)` - A bug fix to not auto-specialize generics during lookup. The problem here was related to an attempted fix of an earlier issue. During checking of a method nested in a generic type, we were running into problems where `DeclRefType::create()` was getting called on an un-specialized reference to `vector`, and this was leading to a crash when the code looked for the arguments for the generic. This was worked around by having name lookup automatically specialize any generics it runs into while going through lookup contexts. That choice creates the problem that in a generic method like this: ``` void test(T val) { ... } ``` any reference to `val` inside the body of `test` will end up getting specialized so that it is effectively `test::val`, when that isn't really needed. - Add front-end logic to check that when a type claims to conform to an interface it actually must provide the methods required by the interface. The checking process goes ahead and builds a front-end "witness table" that maps declarations in the interface being conformed to over to their concrete implementations for the type. - At the moment the checking is completely broken and bad: it assumes that *any* member with the right name is an appropriate declaration to satisfy a requirement. That obviously needs to be fixed. - Add an explicit operation to the IR for lookup of methods: `lookup_interface_method(w, r)` where `w` is a reference to the "witness" value and `r` is an `IRDeclRef` for the member we want to look up. - Add an explicit notion of witness tables to the IR. These end up being the IR representation of an `InheritanceDecl` in a type, and they are generated by enumerating the members that satisfy the interface requirements (which were handily already enumerated by the front-end checking). The witness table is an explicit IR value, and so it will be referenced/used at the site where conformance is being exploited (e.g., as part of a `specialize` call), so it should be safe to eliminate witness tables that are unused (since they represent conformances that aren't actually exploited). Similarly, the entries in a witness table are uses of the functions that implement interface methods, and so keep those live. - In order to implement the above, I did a bit of a cleanup pass on the IR representation so that there is an `IRUser` base that `IRInst` inherits from, so that we can have users of values that aren't instructions. - One annoying thing is that because of how types and generics are handled in the IR, we needed a way to have a type-level `Val` that wraps an IR-level value: e.g., to allow an IR-level witness table to be used as one of the arguments for specialization of a generic. The design I chose here is to have a "proxy" `Val` subclass (`IRProxyVal`) that wraps an `IRValue*`. These should only ever appear as part of types and `DeclRef`s that are used by the IR. - One annoying bit here is that an IR value might then have a use that is not manifest in the set of IR instructions, and instead only appears as part of a type somewhere. - I'm not 100% happy with this design, but it seems like we'd have to tackle similar issues if/when we eventually allow functions to have `constexpr` or `@Constant` parameters - Make generic specialization also propagate witness table arguments through to their use sites (this is mostly just the existing substitution machinery, once we have `IRProxyVal`), and then include logic to specialize `lookup_interface_method` instructions when their first operand is a concrete witness table. All of this work allows a single limited test using generics with constraints to pass, but more work is needed to make the solution robust. --- source/slang/lower-to-ir.cpp | 339 ++++++++++++++++++++++++++++++++----------- 1 file changed, 257 insertions(+), 82 deletions(-) (limited to 'source/slang/lower-to-ir.cpp') diff --git a/source/slang/lower-to-ir.cpp b/source/slang/lower-to-ir.cpp index 327902e4a..2f0ea810e 100644 --- a/source/slang/lower-to-ir.cpp +++ b/source/slang/lower-to-ir.cpp @@ -443,12 +443,62 @@ LoweredValInfo emitPostOp( return LoweredValInfo::ptr(argPtr); } +// Emit a reference to a function, where we have concluded +// that the original AST referenced `funcDeclRef`. The +// optional expression `funcExpr` can provide additional +// detail that might modify how we go about looking up +// the actual value to call. +LoweredValInfo emitFuncRef( + IRGenContext* context, + DeclRef funcDeclRef, + Expr* funcExpr) +{ + if( !funcExpr ) + { + return emitDeclRef(context, funcDeclRef); + } + + // Let's look at the expression to see what additional + // information it gives us. + + if(auto funcMemberExpr = dynamic_cast(funcExpr)) + { + auto baseExpr = funcMemberExpr->BaseExpression; + if(auto baseMemberExpr = baseExpr.As()) + { + auto baseMemberDeclRef = baseMemberExpr->declRef; + if(auto baseConstraintDeclRef = baseMemberDeclRef.As()) + { + // We are calling a method "through" a generic type + // parameter that was constrained to some type. + // That means `funcDeclRef` is a reference to the method + // on the `interface` type (which doesn't actually have + // a body, so we don't want to emit or call it), and + // we actually want to perform a lookup step to + // find the corresponding member on our chosen type. + + RefPtr type = funcExpr->type; + + return LoweredValInfo::simple(context->irBuilder->emitLookupInterfaceMethodInst( + type, + baseMemberDeclRef, + funcDeclRef)); + } + } + } + + // We didn't trigger a special case, so just emit a reference + // to the function itself. + return emitDeclRef(context, funcDeclRef); +} + // Given a `DeclRef` for something callable, along with a bunch of // arguments, emit an appropriate call to it. LoweredValInfo emitCallToDeclRef( IRGenContext* context, IRType* type, DeclRef funcDeclRef, + Expr* funcExpr, UInt argCount, IRValue* const* args) { @@ -572,7 +622,7 @@ LoweredValInfo emitCallToDeclRef( } // Fallback case is to emit an actual call. - LoweredValInfo funcVal = emitDeclRef(context, funcDeclRef); + LoweredValInfo funcVal = emitFuncRef(context, funcDeclRef, funcExpr); return emitCallToVal(context, type, funcVal, argCount, args); } @@ -580,9 +630,10 @@ LoweredValInfo emitCallToDeclRef( IRGenContext* context, IRType* type, DeclRef funcDeclRef, + Expr* funcExpr, List const& args) { - return emitCallToDeclRef(context, type, funcDeclRef, args.Count(), args.Buffer()); + return emitCallToDeclRef(context, type, funcDeclRef, funcExpr, args.Count(), args.Buffer()); } IRValue* getSimpleVal(IRGenContext* context, LoweredValInfo lowered) @@ -611,6 +662,7 @@ top: context, boundSubscriptInfo->type, getter, + nullptr, boundSubscriptInfo->args); goto top; } @@ -660,7 +712,7 @@ struct LoweredTypeInfo } }; -IRType* getSimpleType(LoweredTypeInfo lowered) +RefPtr getSimpleType(LoweredTypeInfo lowered) { switch(lowered.flavor) { @@ -700,7 +752,7 @@ static LoweredTypeInfo lowerType( } // Lower a type and expect the result to be simple -IRType* lowerSimpleType( +RefPtr lowerSimpleType( IRGenContext* context, Type* type) { @@ -708,7 +760,7 @@ IRType* lowerSimpleType( return getSimpleType(lowered); } -IRType* lowerSimpleType( +RefPtr lowerSimpleType( IRGenContext* context, QualType const& type) { @@ -819,7 +871,15 @@ struct ValLoweringVisitor : ValVisitordeclRef); + + return LoweredTypeInfo(type); } @@ -966,6 +1026,16 @@ struct ExprLoweringVisitorBase : ExprVisitor boundMemberInfo->declRef = callableDeclRef; return LoweredValInfo::boundMember(boundMemberInfo); } + else if(auto constraintDeclRef = declRef.As()) + { + // The code is making use of a "witness" that a value of + // some generic type conforms to an interface. + // + // For now we will just emit the base expression as-is. + // TODO: we may need to insert an explicit instruction + // for a cast here (that could become a no-op later). + return loweredBase; + } SLANG_UNIMPLEMENTED_X("codegen for subscript expression"); } @@ -1315,7 +1385,12 @@ struct ExprLoweringVisitorBase : ExprVisitor // require "fixup" work on the other side. // addDirectCallArgs(expr, funcDeclRef, &irArgs, &argFixups); - auto result = emitCallToDeclRef(context, type, funcDeclRef, irArgs); + auto result = emitCallToDeclRef( + context, + type, + funcDeclRef, + funcExpr, + irArgs); applyOutArgumentFixups(argFixups); return result; } @@ -1937,6 +2012,7 @@ top: context, context->getSession()->getVoidType(), setterDeclRef, + nullptr, allArgs); return; } @@ -1972,6 +2048,72 @@ struct DeclLoweringVisitor : DeclVisitor SLANG_UNIMPLEMENTED_X("decl catch-all"); } + LoweredValInfo visitGenericTypeParamDecl(GenericTypeParamDecl* decl) + { + return LoweredValInfo(); + } + + LoweredValInfo visitInheritanceDecl(InheritanceDecl* inheritanceDecl) + { + // Construct a type for the parent declaration. + // + // TODO: if this inheritance declaration is under an extension, + // then we should construct the type that is being extended, + // and not a reference to the extension itself. + auto parentDecl = inheritanceDecl->ParentDecl; + RefPtr type = DeclRefType::Create( + context->getSession(), + makeDeclRef(parentDecl)); + + + // TODO: if the parent type is generic, then I suppose these + // need to be *generic* witness tables? + + // What is the super-type that we have declared we inherit from? + RefPtr superType = inheritanceDecl->base.type; + + // Construct the mangled name for the witness table, which depends + // on the type that is conforming, and the type that it conforms to. + String mangledName = getMangledNameForConformanceWitness( + type, + superType); + + // Build an IR level witness table, which will represent the + // conformance of the type to its super-type. + auto witnessTable = context->irBuilder->createWitnessTable(); + witnessTable->mangledName = mangledName; + + // Register the value now, rather than later, to avoid + // infinite recursion. + context->shared->declValues[inheritanceDecl] = LoweredValInfo::simple(witnessTable); + + + // Semantic checking will have filled in a dictionary of + // witnesses for requirements in the interface, and we + // will now navigate that dictionary to fill in the witness table. + for (auto entry : inheritanceDecl->requirementWitnesses) + { + auto requiredMemberDeclRef = entry.Key; + auto satisfyingMemberDecl = entry.Value; + + auto irRequirement = context->irBuilder->getDeclRefVal(requiredMemberDeclRef); + auto irSatisfyingVal = getSimpleVal(context, ensureDecl(context, satisfyingMemberDecl)); + + auto witnessTableEntry = context->irBuilder->createWitnessTableEntry( + witnessTable, + irRequirement, + irSatisfyingVal); + } + + witnessTable->moveToEnd(); + + // A direct reference to this inheritance relationship (e.g., + // as a subtype witness) will take the form of a reference to + // the witness table in the IR. + return LoweredValInfo::simple(witnessTable); + } + + LoweredValInfo visitDeclGroup(DeclGroup* declGroup) { // To lowere a group of declarations, we just @@ -2141,91 +2283,25 @@ struct DeclLoweringVisitor : DeclVisitor LoweredValInfo visitAggTypeDecl(AggTypeDecl* decl) { -#if 0 - // User-defined aggregate type: need to translate into - // a corresponding IR aggregate type. - - auto builder = getBuilder(); - IRStructDecl* irStruct = builder->createStructType(); - - for (auto fieldDecl : decl->GetFields()) + // Given a declaration of a type, we need to make sure + // to output "witness tables" for any interfaces this + // type has declared conformance to. + for( auto inheritanceDecl : decl->getMembersOfType() ) { - // TODO: need to track relationship to original fields... - - // TODO: need to be prepared to deal with tuple-ness of fields here - auto fieldType = lowerType(context, fieldDecl->getType()); - - switch (fieldType.flavor) - { - case LoweredTypeInfo::Flavor::Simple: - { - auto irField = builder->createStructField(getSimpleType(fieldType)); - builder->addInst(irStruct, irField); - - builder->addHighLevelDeclDecoration(irField, fieldDecl); - - context->shared->declValues.Add( - DeclRef(fieldDecl, nullptr), - LoweredValInfo::simple(irField)); - } - break; - - default: - SLANG_UNIMPLEMENTED_X("struct field type"); - } + ensureDecl(context, inheritanceDecl); } - builder->addHighLevelDeclDecoration(irStruct, decl); - - builder->addInst(irStruct); - - return LoweredValInfo::simple(irStruct); -#else - // TODO: What is there to do with a `struct` type? + // For now, we don't have an IR-level representation + // for the type itself. return LoweredValInfo(); -#endif } - // Sometimes we need to refer to a declaration the way that it would be specialized - // inside the context where it is declared (e.g., with generic parameters filled in - // using their archetypes). - // - RefPtr createDefaultSubstitutions(Decl* decl) - { - auto dd = decl->ParentDecl; - while( dd ) - { - if( auto genericDecl = dynamic_cast(dd) ) - { - auto session = context->getSession(); - - RefPtr subst = new Substitutions(); - subst->genericDecl = genericDecl; - subst->outer = createDefaultSubstitutions(genericDecl); - - for( auto mm : genericDecl->Members ) - { - if( auto genericTypeParamDecl = mm.As() ) - { - subst->args.Add(DeclRefType::Create(session, makeDeclRef(genericTypeParamDecl.Ptr()))); - } - else if( auto genericValueParamDecl = mm.As() ) - { - subst->args.Add(new GenericParamIntVal(makeDeclRef(genericValueParamDecl.Ptr()))); - } - } - return subst; - } - dd = dd->ParentDecl; - } - return nullptr; - } DeclRef createDefaultSpecializedDeclRefImpl(Decl* decl) { DeclRef declRef; declRef.decl = decl; - declRef.substitutions = createDefaultSubstitutions(decl); + declRef.substitutions = createDefaultSubstitutions(context->getSession(), decl); return declRef; } // @@ -2595,7 +2671,7 @@ struct DeclLoweringVisitor : DeclVisitor for( auto paramInfo : parameterLists.params ) { - IRType* irParamType = lowerSimpleType(context, paramInfo.type); + RefPtr irParamType = lowerSimpleType(context, paramInfo.type); switch( paramInfo.direction ) { @@ -2854,6 +2930,97 @@ LoweredValInfo ensureDecl( return result; } +IRWitnessTable* findWitnessTable( + IRGenContext* context, + DeclRef declRef) +{ + IRValue* irVal = getSimpleVal(context, emitDeclRef(context, declRef)); + if (!irVal) + { + SLANG_UNEXPECTED("expected a witness table"); + return nullptr; + } + + if (irVal->op != kIROp_witness_table) + { + // TODO: We might eventually have cases of `specialize` called + // on a witness table... + SLANG_UNEXPECTED("expected a witness table"); + return nullptr; + } + + return (IRWitnessTable*)irVal; +} + +RefPtr lowerSubstitutionArg( + IRGenContext* context, + Val* val) +{ + if (auto type = dynamic_cast(val)) + { + return lowerSimpleType(context, type); + } + else if (auto declaredSubtypeWitness = dynamic_cast(val)) + { + // We need to look up the IR-level representation of the witness + // (which is a witness table). + + auto irWitnessTable = findWitnessTable(context, declaredSubtypeWitness->declRef); + + // We have an IR-level value, but we need to embed it into an AST-level + // type, so we will use a proxy `Val` that wraps up an `IRValue` as + // an AST-level value. + // + // TODO: This proxy value currently doesn't enter into use-def chaining, + // and so Bad Things could happen quite easily. We need to fix that + // up in a reasonably clean fashion. + // + RefPtr proxyVal = new IRProxyVal(); + proxyVal->inst = irWitnessTable; + return proxyVal; + } + else + { + // For now, jsut assume that all other values + // lower to themselves. + // + // TODO: we should probably handle the case of + // a `Val` that references an AST-level `constexpr` + // variable, since that would need to be lowered + // to a `Val` that references the IR equivalent. + return val; + } +} + +// Given a set of substitutions, make sure that we have +// lowered the arguments being used into a form that +// is suitable for use in the IR. +RefPtr lowerSubstitutions( + IRGenContext* context, + Substitutions* subst) +{ + if(!subst) + return nullptr; + + RefPtr newSubst = new Substitutions(); + if (subst->outer) + { + newSubst->outer = lowerSubstitutions( + context, + subst->outer); + } + + newSubst->genericDecl = subst->genericDecl; + + for (auto arg : subst->args) + { + auto newArg = lowerSubstitutionArg(context, arg); + newSubst->args.Add(newArg); + } + + return newSubst; +} + LoweredValInfo emitDeclRef( IRGenContext* context, DeclRef declRef) @@ -2869,6 +3036,14 @@ LoweredValInfo emitDeclRef( auto val = getSimpleVal(context, loweredDecl); + // We have the "raw" substitutions from the AST, but we may + // need to walk through those and replace things in + // cases where the `Val`s used for substitution should + // lower to something other than their original form. + RefPtr newSubst = lowerSubstitutions(context, declRef.substitutions); + declRef.substitutions = newSubst; + + RefPtr type; if(auto declType = val->getType()) { -- cgit v1.2.3