From 7eaaf1aa1fdac3fd7ff7b64800a965a2b2c17f66 Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Thu, 22 Feb 2018 11:44:57 -0800 Subject: Initial work on validating "constexpr"-ness in IR (#420) * Initial work on validating "constexpr"-ness in IR The underlying issue here is that certain operations in the target shading languages constrain their operands to be compile-time constants. A notable example is the optional texel offset parameter to the `Texture2D.Sample` operation. When calling these operations in GLSL, the user is required to pass a "constant expression," and any variables in that expression must therefore be marked with the `const` qualifier (and themselves be initialized with constant expressions). Any GLSL output we generate must of course respect these rules. When calling these operations in HLSL, the user is not so constrained. Instead, they can pass an arbitrary expression, which may involve ordinary variables with no particular markup, and then the compiler is responsible for determining if the actual value after simplification works out to be a constant. In some cases, the requirement that a value be constant might actually trigger things like loop unrolling. Also, it is okay to use a function parameter to determine such a constant expression, as long as the argument turns out to be a constant at all call sites. The way we have decided to tackle these challenges in Slang is that we we propagate a notion of `constexpr`-ness through the IR. This is currently being tackled in `ir-constexpr.cpp` with a combination of forward and backward iterative dataflow: * When the operands to an instruction are all `constexpr`, and the opcode is one we believe can be constant-folded, then we infer that the instruction *can* be evaluated as `constexpr` * When instruction is required to be `constexpr`, then we infer that all of its operands are also required to be `constexpr`. If this process ever infers that a function parameter is required to be `constexpr`, then we might have to continue propagation at all the call sites to that function. If after all the propagation is done, there are any cases where an instruction is *required* to be `constexpr`, but it *can't* be `constexpr` (we weren't able to infer `constexpr`-ness for its operands), then we issue an error. This implementation encodes the idea of `constexpr`-ness in the IR as part of the type system, using a simplified notion of rates. This change adds a `RateQualifiedType` that can represent `@R T`, and then introduces a `ConstExprRate` that can be used for `R`. Many accessors for the type information on IR nodes were updated to distinguish when one wants the "full" type of an IR value (which might include rate information) vs. just the "data" type. A `constexpr` qualifier was added in the front-end, and is being used to decorate the texel offset parameter for `Texture2D.Sample`. Lowering from AST to IR looks for this qalifier and infers when a function parameter must be typed as `@ConstExpr T` instead of just `T`. There are lots of limitations and gotchas in the implementation so far: * The `@ConstExpr` rate is the only one added in this change, but it seems clear that the conceptual `ThreadGroup` rate that was added to represent `groupshared` should probably get folded into the representation. * I'm not 100% pleased with how many places in the IR I have to special-case for rate-qualified types. At the same type, pulling out rate as a distinct field on `IRValue` would probably require that we pay attention to rate everywhere. * I've added a test case to show that we can issue errors when users fail to provide a constant expression for the texel offset, but the actual error message isn't great because it doesn't indicate *why* a constant expression was required. Realistically the "initial IR" should contain a few more decorations we can use to relate error conditions back to the original code (even if this is in a side-band structure). * I've added a test case that is supposed to show that we can back-propagate `constexpr`-ness to local variables, and I've manually confirmed that it works for Vulkan/SPIR-V output, but the level of Vulkan support in `render_test` today means I can't enable the test for check-in. * While I'm attempting to propagate `@ConstExpr` information from callees to callers, I haven't implemented any logic to specialize callee functions based on values at call sites. * In a similar vein, there is no handling of control-flow dependence in the current code. If we infer that a phi (block parameter) needs to be `@ConstExpr`, then it isn't actually enough to require that the inputs to the phi (arguments from predecessor blocks) are all `@ConstExpr` because we also need any control-flow decisions that pick which incoming edge we take to be `@ConstExpr` as well. * As a practical matter, implicit propagation of `@ConstExpr` from a function body to a function parameter should only be allowed for functions that are "local" to a module. Any function that might be accessed from outside of a module should really have had its `@ConstExpr` parameter marked manually, and our pass should validate that they follow their own rules. Right now we have no kind of visibility (`public` vs `private`) system, so I'm kind of ignoring this issue. While that is a lot of gaps, this is also just enough code to get the Falcor MultiPassPostProcess example working, so I'm inclined to get it checked in. * Fixup: missing expected output for test * Fixup: disable test that relies on [unroll] for now --- source/slang/ir-constexpr.cpp | 531 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 531 insertions(+) create mode 100644 source/slang/ir-constexpr.cpp (limited to 'source/slang/ir-constexpr.cpp') diff --git a/source/slang/ir-constexpr.cpp b/source/slang/ir-constexpr.cpp new file mode 100644 index 000000000..f5738c036 --- /dev/null +++ b/source/slang/ir-constexpr.cpp @@ -0,0 +1,531 @@ +// ir-constexpr.cpp +#include "ir-constexpr.h" + +#include "ir.h" +#include "ir-insts.h" + +namespace Slang { + +struct PropagateConstExprContext +{ + DiagnosticSink* sink; + + SharedIRBuilder sharedBuilder; + IRBuilder builder; + + List workList; + HashSet onWorkList; + + IRBuilder* getBuilder() { return &builder; } + + Session* getSession() { return sharedBuilder.session; } + + DiagnosticSink* getSink() { return sink; } +}; + +bool isConstExpr(Type* type) +{ + if( auto rateQualifiedType = type->As() ) + { + auto rate = rateQualifiedType->rate; + if(auto constExprRate = rate->As()) + return true; + } + + return false; +} + +bool isConstExpr(IRValue* value) +{ + // Certain IR value ops are implicitly `constexpr` + // + // TODO: should we just go ahead and make that explicit + // in the type system? + switch(value->op) + { + case kIROp_IntLit: + case kIROp_FloatLit: + case kIROp_boolConst: + case kIROp_Func: + return true; + + default: + break; + } + + if(isConstExpr(value->getFullType())) + return true; + + return false; +} + +bool opCanBeConstExpr(IROp op) +{ + switch( op ) + { + case kIROp_IntLit: + case kIROp_FloatLit: + case kIROp_boolConst: + case kIROp_Add: + case kIROp_Sub: + case kIROp_Mul: + case kIROp_Div: + case kIROp_Mod: + case kIROp_Neg: + case kIROp_Construct: + case kIROp_makeVector: + case kIROp_makeArray: + case kIROp_makeMatrix: + // TODO: more cases + return true; + + default: + return false; + } +} + +bool opCanBeConstExpr(IRValue* value) +{ + // TODO: realistically need to special-case `call` + // operations here, so that we check whether the + // callee function is fixed/known, and if it is + // whether it has been decoared as constant-foldable + + return opCanBeConstExpr(value->op); +} + +void markConstExpr( + PropagateConstExprContext* context, + IRValue* value) +{ + Slang::markConstExpr(context->getSession(), value); +} + + +// Propagate `constexpr`-ness in a forward direction, from the +// operands of an instruction to the instruction itself. +bool propagateConstExprForward( + PropagateConstExprContext* context, + IRGlobalValueWithCode* code) +{ + bool anyChanges = false; + for(;;) + { + bool changedThisIteration = false; + for( auto bb = code->getFirstBlock(); bb; bb = bb->getNextBlock() ) + { + for( auto ii = bb->getFirstInst(); ii; ii = ii->getNextInst() ) + { + // Instruction already `constexpr`? Then skip it. + if(isConstExpr(ii)) + continue; + + // Is the operation one that we can actually make be constexpr? + if(!opCanBeConstExpr(ii)) + continue; + + // Are all arguments `constexpr`? + bool allArgsConstExpr = true; + UInt argCount = ii->getArgCount(); + for( UInt aa = 0; aa < argCount; ++aa ) + { + auto arg = ii->getArg(aa); + + if( !isConstExpr(arg) ) + { + allArgsConstExpr = false; + break; + } + } + if(!allArgsConstExpr) + continue; + + // Seems like this operation can/should be made constexpr + markConstExpr(context, ii); + changedThisIteration = true; + } + } + + if( !changedThisIteration ) + return anyChanges; + + anyChanges = true; + } +} + +void maybeAddToWorkList( + PropagateConstExprContext* context, + IRGlobalValue* gv) +{ + if( !context->onWorkList.Contains(gv) ) + { + context->workList.Add(gv); + context->onWorkList.Add(gv); + } +} + +bool maybeMarkConstExpr( + PropagateConstExprContext* context, + IRValue* value) +{ + if(isConstExpr(value)) + return false; + + if(!opCanBeConstExpr(value)) + return false; + + markConstExpr(context, value); + + // TODO: we should only allow function parameters to be + // changed to be `constexpr` when we are compiling "application" + // code, and not library code. + // (Or eventually we'd have a rule that only non-`public` symbols + // can have this kind of propagation applied). + + if(value->op == kIROp_Param) + { + auto param = (IRParam*) value; + auto block = (IRBlock*) param->parent; + auto code = block->getParent(); + + if(block == code->getFirstBlock()) + { + // We've just changed a function parameter to + // be `constexpr`. We need to remember that + // fact so taht we can mark callers of this + // function as `constexpr` themselves. + + for( auto u = code->firstUse; u; u = u->nextUse ) + { + auto user = u->getUser(); + + switch( user->op ) + { + case kIROp_Call: + { + auto inst = (IRCall*) user; + auto caller = inst->getParentBlock()->getParent(); + maybeAddToWorkList(context, caller); + } + break; + + default: + break; + } + } + } + } + + return true; +} + +// Propagate `constexpr`-ness in a backward direction, from an instruction +// to its operands. +bool propagateConstExprBackward( + PropagateConstExprContext* context, + IRGlobalValueWithCode* code) +{ + SharedIRBuilder sharedBuilder; + sharedBuilder.module = code->parentModule; + sharedBuilder.session = sharedBuilder.module->session; + + IRBuilder builder; + builder.sharedBuilder = &sharedBuilder; + builder.curFunc = code; + builder.curBlock = nullptr; + + bool anyChanges = false; + for(;;) + { + // Note: we are walking the list of blocks and the instructions + // in each block in reverse order, to maximize the chances that + // we propagate multiple changes in a each pass. + // + // TODO: this should probably all be done with a work list instead, + // but that requires being able to detect instructions vs. other + // values. + + bool changedThisIteration = false; + for( auto bb = code->getLastBlock(); bb; bb = bb->getPrevBlock() ) + { + for( auto ii = bb->getLastInst(); ii; ii = ii->getPrevInst() ) + { + if( isConstExpr(ii) ) + { + // If this instruction is `constexpr`, then its operands should be too. + UInt argCount = ii->getArgCount(); + for( UInt aa = 0; aa < argCount; ++aa ) + { + auto arg = ii->getArg(aa); + if(isConstExpr(arg)) + continue; + + if(!opCanBeConstExpr(arg)) + continue; + + if( maybeMarkConstExpr(context, arg) ) + { + changedThisIteration = true; + } + } + } + else if( ii->op == kIROp_Call ) + { + // A non-constexpr call might be calling a function with one or + // more constexpr parameters. We should check if we can resolve + // the callee for this call statically, and if so try to propagate + // constexpr from the parameters back to the arguments. + auto callInst = (IRCall*) ii; + + UInt operandCount = callInst->getArgCount(); + + UInt firstCallArg = 1; + UInt callArgCount = operandCount - firstCallArg; + + auto callee = callInst->getArg(0); + while( callee->op == kIROp_specialize ) + { + callee = ((IRSpecialize*) callee)->getArg(0); + } + if( callee->op == kIROp_Func ) + { + auto calleeFunc = (IRFunc*) callee; + auto calleeFuncType = calleeFunc->getType(); + + UInt callParamCount = calleeFuncType->getParamCount(); + SLANG_RELEASE_ASSERT(callParamCount == callArgCount); + + // If the callee has a definition, then we can read `constexpr` + // information off of the parameters of its first IR block. + if( auto calleeFirstBlock = calleeFunc->firstBlock ) + { + UInt paramCounter = 0; + for( auto pp = calleeFirstBlock->getFirstParam(); pp; pp = pp->getNextParam() ) + { + UInt paramIndex = paramCounter++; + + auto param = pp; + auto arg = callInst->getArg(firstCallArg + paramIndex); + + if( isConstExpr(param) ) + { + if( maybeMarkConstExpr(context, arg) ) + { + changedThisIteration = true; + } + } + } + } + else + { + // If we don't have the definition/body for the callee, + // then we have to glean `constexpr` information from its + // type instead. + auto calleeType = calleeFunc->getType(); + auto paramCount = calleeType->getParamCount(); + for( UInt pp = 0; pp < paramCount; ++pp ) + { + auto paramType = calleeType->getParamType(pp); + auto arg = callInst->getArg(firstCallArg + pp); + if( isConstExpr(paramType) ) + { + if( maybeMarkConstExpr(context, arg) ) + { + changedThisIteration = true; + } + } + } + } + + // TODO: this currently only works if the callee has a definition, + // because that is the only case where will generate IR values for + // its parameter list. Otherwise we'd need to pull this information + // from the function *type* for builtins. + if(!calleeFunc->firstBlock) + continue; + + } + } + } + + if( bb != code->getFirstBlock() ) + { + // A parameter in anything butr the first block is + // conceptually a phi node, which means its operands + // are the corresponding values from the terminating + // branch in a predecessor block. + + UInt paramCounter = 0; + for( auto pp = bb->getFirstParam(); pp; pp = pp->getNextParam() ) + { + UInt paramIndex = paramCounter++; + + if(!isConstExpr(pp)) + continue; + + for(auto pred : bb->getPredecessors()) + { + auto terminator = pred->getLastInst(); + if(terminator->op != kIROp_unconditionalBranch) + continue; + + UInt operandIndex = paramIndex + 1; + SLANG_RELEASE_ASSERT(operandIndex < terminator->getArgCount()); + + auto operand = terminator->getArg(operandIndex); + if( maybeMarkConstExpr(context, operand) ) + { + changedThisIteration = true; + } + } + } + } + + } + + if( !changedThisIteration ) + return anyChanges; + + anyChanges = true; + } +} + +// Validate use of `constexpr` within a function (in particular, +// diagnose places where a value that must be contexpr depends +// on a value that cannot be) +void validateConstExpr( + PropagateConstExprContext* context, + IRGlobalValueWithCode* code) +{ + for( auto bb = code->getFirstBlock(); bb; bb = bb->getNextBlock() ) + { + for( auto ii = bb->getFirstInst(); ii; ii = ii->getNextInst() ) + { + if(isConstExpr(ii)) + { + // For an instruction that must be `constexpr`, we need + // to ensure that its argumenst are all `constexpr` + + UInt argCount = ii->getArgCount(); + for( UInt aa = 0; aa < argCount; ++aa ) + { + auto arg = ii->getArg(aa); + + if( !isConstExpr(arg) ) + { + // Diagnose the failure. + + context->getSink()->diagnose(ii->sourceLoc, Diagnostics::needCompileTimeConstant); + + break; + } + } + } + } + } +} + +void propagateConstExpr( + IRModule* module, + DiagnosticSink* sink) +{ + auto session = module->session; + + PropagateConstExprContext context; + context.sink = sink; + context.sharedBuilder.module = module; + context.sharedBuilder.session = session; + context.builder.sharedBuilder = &context.sharedBuilder; + context.builder.curFunc = nullptr; + context.builder.curBlock = nullptr; + + + + // We need to propagate information both forward and backward. + // + // In the forward direction we need to check if all of the operands + // to an instruction are `constexpr` *and* if the operation is + // one that can conceptually be "promoted" to the constexpr rate. + // + // In the backward direction, if an instruction has already been + // marked as needing to be `constexpr`, then its operands had + // better be too. + // + // The backward direction needs to be interprocedural, because + // a parameter to a function might be `constexpr`, so that callers + // of that function would need to be marked too. If backwards + // propagation in any of the callers leads to some of their + // parameters being marked constexpr, then we would need to + // revisit their callers. + + // We will build an initial work list with all of the global values in it. + + for( auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue() ) + { + maybeAddToWorkList(&context, gv); + } + + // We will iterate applying propagation to one global value at a time + // until we run out. + while( context.workList.Count() ) + { + auto gv = context.workList[0]; + context.workList.FastRemoveAt(0); + context.onWorkList.Remove(gv); + + switch( gv->op ) + { + default: + break; + + case kIROp_Func: + case kIROp_global_var: + case kIROp_global_constant: + { + IRGlobalValueWithCode* code = (IRGlobalValueWithCode*) gv; + + for( ;;) + { + bool anyChange = false; + if( propagateConstExprForward(&context, code) ) + { + anyChange = true; + } + if( propagateConstExprBackward(&context, code) ) + { + anyChange = true; + } + if(!anyChange) + break; + } + } + break; + } + } + + // Okay, we've processed all our functions and found a steady state. + // Now we need to try and issue diagnostics for any IR values where + // we find that they are *required* to be `constexpr`, but *cannot* + // be, for some reason. + + for( auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue() ) + { + switch( gv->op ) + { + default: + break; + + case kIROp_Func: + case kIROp_global_var: + case kIROp_global_constant: + { + IRGlobalValueWithCode* code = (IRGlobalValueWithCode*) gv; + validateConstExpr(&context, code); + } + break; + } + } + +} + +} -- cgit v1.2.3