// slang-ir.cpp
#include "slang-ir.h"
#include "../core/slang-basic.h"
#include "../core/slang-platform.h"
#include "../core/slang-writer.h"
#include "slang-ir-dominators.h"
#include "slang-ir-insts.h"
#include "slang-ir-util.h"
#include "slang-mangle.h"
namespace Slang
{
struct IRSpecContext;
// !!!!!!!!!!!!!!!!!!!!!!!!!!!! DiagnosticSink Impls !!!!!!!!!!!!!!!!!!!!!
SourceLoc const& getDiagnosticPos(IRInst* inst)
{
while (inst)
{
if (inst->sourceLoc.isValid())
return inst->sourceLoc;
inst = inst->parent;
}
static SourceLoc invalid = SourceLoc();
return invalid;
}
void printDiagnosticArg(StringBuilder& sb, IRInst* irObject)
{
if (!irObject)
return;
if (as<IRType>(irObject))
{
getTypeNameHint(sb, irObject);
return;
}
if (auto nameHint = irObject->findDecoration<IRNameHintDecoration>())
{
sb << nameHint->getName();
return;
}
if (auto linkage = irObject->findDecoration<IRLinkageDecoration>())
{
sb << linkage->getMangledName();
return;
}
}
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
bool isSimpleDecoration(IROp op)
{
switch (op)
{
case kIROp_EarlyDepthStencilDecoration:
case kIROp_KeepAliveDecoration:
case kIROp_LineAdjInputPrimitiveTypeDecoration:
case kIROp_LineInputPrimitiveTypeDecoration:
case kIROp_NoInlineDecoration:
case kIROp_DerivativeGroupQuadDecoration:
case kIROp_DerivativeGroupLinearDecoration:
case kIROp_PointInputPrimitiveTypeDecoration:
case kIROp_PreciseDecoration:
case kIROp_PublicDecoration:
case kIROp_HLSLExportDecoration:
case kIROp_ReadNoneDecoration:
case kIROp_NoSideEffectDecoration:
case kIROp_ForwardDifferentiableDecoration:
case kIROp_BackwardDifferentiableDecoration:
case kIROp_RequiresNVAPIDecoration:
case kIROp_TriangleAdjInputPrimitiveTypeDecoration:
case kIROp_TriangleInputPrimitiveTypeDecoration:
case kIROp_UnsafeForceInlineEarlyDecoration:
case kIROp_VulkanCallablePayloadDecoration:
case kIROp_VulkanCallablePayloadInDecoration:
case kIROp_VulkanHitAttributesDecoration:
case kIROp_VulkanRayPayloadDecoration:
case kIROp_VulkanRayPayloadInDecoration:
case kIROp_VulkanHitObjectAttributesDecoration:
{
return true;
}
default:
break;
}
return false;
}
IRInst* cloneGlobalValueWithLinkage(
IRSpecContext* context,
IRInst* originalVal,
IRLinkageDecoration* originalLinkage);
//
void IRUse::debugValidate()
{
#ifdef _DEBUG
auto uv = this->usedValue;
if (!uv)
{
assert(!nextUse);
assert(!prevLink);
return;
}
auto pp = &uv->firstUse;
for (auto u = uv->firstUse; u;)
{
assert(u->prevLink == pp);
pp = &u->nextUse;
u = u->nextUse;
}
#endif
}
void IRUse::init(IRInst* u, IRInst* v)
{
clear();
user = u;
usedValue = v;
if (v)
{
nextUse = v->firstUse;
prevLink = &v->firstUse;
if (nextUse)
{
nextUse->prevLink = &this->nextUse;
}
v->firstUse = this;
}
#ifdef SLANG_ENABLE_FULL_IR_VALIDATION
debugValidate();
#endif
}
void IRUse::set(IRInst* uv)
{
// Normally we should never be modifying the operand of an hoistable inst.
// They can be modified by `replaceUsesWith`, or to be replaced by a new inst.
SLANG_ASSERT(!getIROpInfo(user->getOp()).isHoistable() || uv == usedValue);
init(user, uv);
}
void IRUse::clear()
{
// This `IRUse` is part of the linked list
// of uses for `usedValue`.
#ifdef SLANG_ENABLE_FULL_IR_VALIDATION
debugValidate();
#endif
if (usedValue)
{
#ifdef SLANG_ENABLE_FULL_IR_VALIDATION
auto uv = usedValue;
#endif
*prevLink = nextUse;
if (nextUse)
{
nextUse->prevLink = prevLink;
}
user = nullptr;
usedValue = nullptr;
nextUse = nullptr;
prevLink = nullptr;
#ifdef SLANG_ENABLE_FULL_IR_VALIDATION
if (uv->firstUse)
uv->firstUse->debugValidate();
#endif
}
}
// IRInstListBase
void IRInstListBase::Iterator::operator++()
{
if (inst)
{
inst = inst->next;
}
}
IRInstListBase::Iterator IRInstListBase::begin()
{
return Iterator(first);
}
IRInstListBase::Iterator IRInstListBase::end()
{
return Iterator(last ? last->next : nullptr);
}
//
IRUse* IRInst::getOperands()
{
// We assume that *all* instructions are laid out
// in memory such that their arguments come right
// after the first `sizeof(IRInst)` bytes.
//
// TODO: we probably need to be careful and make
// this more robust.
return (IRUse*)(this + 1);
}
IRDecoration* IRInst::findDecorationImpl(IROp decorationOp)
{
for (auto dd : getDecorations())
{
if (dd->getOp() == decorationOp)
return dd;
}
return nullptr;
}
IROperandList<IRAttr> IRInst::getAllAttrs()
{
// We assume as an invariant that all attributes appear at the end of the operand
// list, after all the non-attribute operands.
//
// We will therefore define a range that ends at the end of the operand list ...
//
IRUse* end = getOperands() + getOperandCount();
//
// ... and begins after the last non-attribute operand.
//
IRUse* cursor = getOperands();
while (cursor != end && !as<IRAttr>(cursor->get()))
cursor++;
return IROperandList<IRAttr>(cursor, end);
}
// IRConstant
IRIntegerValue getIntVal(IRInst* inst)
{
switch (inst->getOp())
{
default:
SLANG_UNEXPECTED("needed a known integer value");
UNREACHABLE_RETURN(0);
case kIROp_IntLit:
return static_cast<IRConstant*>(inst)->value.intVal;
break;
}
}
IRIntegerValue getArraySizeVal(IRInst* inst)
{
switch (inst->getOp())
{
case kIROp_IntLit:
return static_cast<IRConstant*>(inst)->value.intVal;
break;
default:
// Treat specialization constant array as the unsized array here.
if (isSpecConstRateType(inst->getFullType()))
return kUnsizedArrayMagicLength;
SLANG_UNEXPECTED("needed a known integer value");
UNREACHABLE_RETURN(0);
}
}
// IRCapabilitySet
CapabilitySet IRCapabilitySet::getCaps()
{
switch (getOp())
{
case kIROp_CapabilityConjunction:
{
List<CapabilityName> atoms;
Index count = (Index)getOperandCount();
for (Index i = 0; i < count; ++i)
{
auto operand = cast<IRIntLit>(getOperand(i));
atoms.add(CapabilityName(operand->getValue()));
}
return CapabilitySet(atoms.getCount(), atoms.getBuffer());
}
break;
case kIROp_CapabilityDisjunction:
{
CapabilitySet result;
Index count = (Index)getOperandCount();
for (Index i = 0; i < count; ++i)
{
auto operand = cast<IRCapabilitySet>(getOperand(i));
result.unionWith(operand->getCaps());
}
return result;
}
break;
}
return CapabilitySet();
}
// IRParam
IRParam* IRParam::getNextParam()
{
return as<IRParam, IRDynamicCastBehavior::NoUnwrap>(getNextInst());
}
IRParam* IRParam::getPrevParam()
{
return as<IRParam, IRDynamicCastBehavior::NoUnwrap>(getPrevInst());
}
// IRArrayTypeBase
IRInst* IRArrayTypeBase::getElementCount()
{
if (auto arrayType = as<IRArrayType>(this))
return arrayType->getOperand(1);
return nullptr;
}
// IRPtrTypeBase
IRType* tryGetPointedToType(IRBuilder* builder, IRType* type)
{
if (auto rateQualType = as<IRRateQualifiedType>(type))
{
type = rateQualType->getValueType();
}
// The "true" pointers and the pointer-like core module types are the easy cases.
if (auto ptrType = as<IRPtrTypeBase>(type))
{
return ptrType->getValueType();
}
else if (auto ptrLikeType = as<IRPointerLikeType>(type))
{
return ptrLikeType->getElementType();
}
//
// A more interesting case arises when we have a `BindExistentials<P<T>, ...>`
// where `P<T>` is a pointer(-like) type.
//
else if (auto bindExistentials = as<IRBindExistentialsType>(type))
{
// We know that `BindExistentials` won't introduce its own
// existential type parameters, nor will any of the pointer(-like)
// type constructors `P`.
//
// Thus we know that the type that is pointed to should be
// the same as `BindExistentials<T, ...>`.
//
auto baseType = bindExistentials->getBaseType();
if (auto baseElementType = tryGetPointedToType(builder, baseType))
{
UInt existentialArgCount = bindExistentials->getExistentialArgCount();
List<IRInst*> existentialArgs;
for (UInt ii = 0; ii < existentialArgCount; ++ii)
{
existentialArgs.add(bindExistentials->getExistentialArg(ii));
}
return builder->getBindExistentialsType(
baseElementType,
existentialArgCount,
existentialArgs.getBuffer());
}
}
// TODO: We may need to handle other cases here.
return nullptr;
}
// IRBlock
IRParam* IRBlock::getLastParam()
{
IRParam* param = getFirstParam();
if (!param)
return nullptr;
while (auto nextParam = param->getNextParam())
param = nextParam;
return param;
}
void IRBlock::addParam(IRParam* param)
{
// If there are any existing parameters,
// then insert after the last of them.
//
if (auto lastParam = getLastParam())
{
if (lastParam->next)
param->insertAfter(lastParam);
else
param->insertAtEnd(this);
}
//
// Otherwise, if there are any existing
// "ordinary" instructions, insert before
// the first of them.
//
else if (auto firstOrdinary = getFirstOrdinaryInst())
{
param->insertBefore(firstOrdinary);
}
//
// Otherwise the block currently has neither
// parameters nor orindary instructions,
// so we can safely insert at the end of
// the list of (raw) children.
//
else
{
param->insertAtEnd(this);
}
}
// Similar to addParam, but instead of appending `param` to the end
// of the parameter list, this function inserts `param` before the
// head of the list.
void IRBlock::insertParamAtHead(IRParam* param)
{
if (auto firstParam = getFirstParam())
{
param->insertBefore(firstParam);
}
else if (auto firstOrdinary = getFirstOrdinaryInst())
{
param->insertBefore(firstOrdinary);
}
else
{
param->insertAtEnd(this);
}
}
IRInst* IRBlock::getFirstOrdinaryInst()
{
// Find the last parameter (if any) of the block
auto lastParam = getLastParam();
if (lastParam)
{
// If there is a last parameter, then the
// instructions after it are the ordinary
// instructions.
return lastParam->getNextInst();
}
else
{
// If there isn't a last parameter, then
// there must not have been *any* parameters,
// and so the first instruction in the block
// is also the first ordinary one.
return getFirstInst();
}
}
IRInst* IRBlock::getLastOrdinaryInst()
{
// Under normal circumstances, the last instruction
// in the block is also the last ordinary instruction.
// However, there is the special case of a block with
// only parameters (which might happen as a temporary
// state while we are building IR).
auto inst = getLastInst();
// If the last instruction is a parameter, then
// there are no ordinary instructions, so the last
// one is a null pointer.
if (as<IRParam, IRDynamicCastBehavior::NoUnwrap>(inst))
return nullptr;
// Otherwise the last instruction is the last "ordinary"
// instruction as well.
return inst;
}
// The predecessors of a block should all show up as users
// of its value, so rather than explicitly store the CFG,
// we will recover it on demand from the use-def information.
//
// Note: we are really iterating over incoming/outgoing *edges*
// for a block, because there might be multiple uses of a block,
// if more than one way of an N-way branch targets the same block.
// Get the list of successor blocks for an instruction,
// which we expect to be the last instruction in a block.
static IRBlock::SuccessorList getSuccessors(IRInst* terminator)
{
// If the block somehow isn't terminated, then
// there is no way to read its successors, so
// we return an empty list.
if (!terminator || !as<IRTerminatorInst>(terminator))
return IRBlock::SuccessorList(nullptr, nullptr);
// Otherwise, based on the opcode of the terminator
// instruction, we will build up our list of uses.
IRUse* begin = nullptr;
IRUse* end = nullptr;
UInt stride = 1;
auto operands = terminator->getOperands();
switch (terminator->getOp())
{
case kIROp_Return:
case kIROp_Unreachable:
case kIROp_MissingReturn:
case kIROp_GenericAsm:
break;
case kIROp_UnconditionalBranch:
case kIROp_Loop:
// unconditonalBranch <block>
begin = operands + 0;
end = begin + 1;
break;
case kIROp_ConditionalBranch:
case kIROp_IfElse:
// conditionalBranch <condition> <trueBlock> <falseBlock>
begin = operands + 1;
end = begin + 2;
break;
case kIROp_Switch:
// switch <val> <break> <default> <caseVal1> <caseBlock1> ...
begin = operands + 2;
// TODO: this ends up point one *after* the "one after the end"
// location, so we should really change the representation
// so that we don't need to form this pointer...
end = operands + terminator->getOperandCount() + 1;
stride = 2;
break;
case kIROp_TargetSwitch:
begin = operands + 2;
end = operands + terminator->getOperandCount() + 1;
stride = 2;
break;
case kIROp_Defer:
// defer <deferBlock> <mergeBlock> <scopeEndBlock>
begin = operands + 0;
end = begin + 1;
break;
case kIROp_TryCall:
// tryCall <successBlock> <failBlock> <callee> <args>...
begin = operands + 0;
end = begin + 2;
break;
default:
SLANG_UNEXPECTED("unhandled terminator instruction");
UNREACHABLE_RETURN(IRBlock::SuccessorList(nullptr, nullptr));
}
return IRBlock::SuccessorList(begin, end, stride);
}
static IRUse* adjustPredecessorUse(IRUse* use)
{
// We will search until we either find a
// suitable use, or run out of uses.
for (; use; use = use->nextUse)
{
// We only want to deal with uses that represent
// a "sucessor" operand to some terminator instruction.
// We will re-use the logic for getting the successor
// list from such an instruction.
auto successorList = getSuccessors((IRInst*)use->getUser());
if (use >= successorList.begin_ && use < successorList.end_)
{
UInt index = (use - successorList.begin_);
if ((index % successorList.stride) == 0)
{
// This use is in the range of the sucessor list,
// and so it represents a real edge between
// blocks.
return use;
}
}
}
// If we ran out of uses, then we are at the end
// of the list of incoming edges.
return nullptr;
}
IRBlock::PredecessorList IRBlock::getPredecessors()
{
// We want to iterate over the predecessors of this block.
// First, we resign ourselves to iterating over the
// incoming edges, rather than the blocks themselves.
// This might sound like a trival distinction, but it is
// possible for there to be multiple edges between two
// blocks (as for a `switch` with multiple cases that
// map to the same code). Any client that wants just
// the unique predecessor blocks needs to deal with
// the deduplication themselves.
//
// Next, we note that for any predecessor edge, there will
// be a use of this block in the terminator instruction of
// the predecessor. We basically just want to iterate over
// the users of this block, then, but we need to be careful
// to rule out anything that doesn't actually represent
// an edge. The `adjustPredecessorUse` function will be
// used to search for a use that actually represents an edge.
return PredecessorList(adjustPredecessorUse(firstUse));
}
UInt IRBlock::PredecessorList::getCount()
{
UInt count = 0;
for (auto ii : *this)
{
(void)ii;
count++;
}
return count;
}
bool IRBlock::PredecessorList::isEmpty()
{
return !(begin() != end());
}
void IRBlock::PredecessorList::Iterator::operator++()
{
if (!use)
return;
use = adjustPredecessorUse(use->nextUse);
}
IRBlock* IRBlock::PredecessorList::Iterator::operator*()
{
if (!use)
return nullptr;
return (IRBlock*)use->getUser()->parent;
}
IRBlock::SuccessorList IRBlock::getSuccessors()
{
// The successors of a block will all be listed
// as operands of its terminator instruction.
// Depending on the terminator, we might have
// different numbers of operands to deal with.
//
// (We might also have to deal with a "stride"
// in the case where the basic-block operands
// are mixed up with non-block operands)
auto terminator = getLastInst();
return Slang::getSuccessors(terminator);
}
UInt IRBlock::SuccessorList::getCount()
{
UInt count = 0;
for (auto ii : *this)
{
(void)ii;
count++;
}
return count;
}
void IRBlock::SuccessorList::Iterator::operator++()
{
use += stride;
}
IRBlock* IRBlock::SuccessorList::Iterator::operator*()
{
return (IRBlock*)use->get();
}
UInt IRUnconditionalBranch::getArgCount()
{
switch (getOp())
{
case kIROp_UnconditionalBranch:
return getOperandCount() - 1;
case kIROp_Loop:
return getOperandCount() - 3;
default:
SLANG_UNEXPECTED("unhandled unconditional branch opcode");
UNREACHABLE_RETURN(0);
}
}
IRUse* IRUnconditionalBranch::getArgs()
{
switch (getOp())
{
case kIROp_UnconditionalBranch:
return getOperands() + 1;
case kIROp_Loop:
return getOperands() + 3;
default:
SLANG_UNEXPECTED("unhandled unconditional branch opcode");
UNREACHABLE_RETURN(0);
}
}
void IRUnconditionalBranch::removeArgument(UInt index)
{
switch (getOp())
{
case kIROp_UnconditionalBranch:
removeOperand(1 + index);
break;
case kIROp_Loop:
removeOperand(3 + index);
break;
default:
SLANG_UNEXPECTED("unhandled unconditional branch opcode");
}
}
IRInst* IRUnconditionalBranch::getArg(UInt index)
{
return getArgs()[index].usedValue;
}
IRParam* IRGlobalValueWithParams::getFirstParam()
{
auto entryBlock = getFirstBlock();
if (!entryBlock)
return nullptr;
return entryBlock->getFirstParam();
}
IRParam* IRGlobalValueWithParams::getLastParam()
{
auto entryBlock = getFirstBlock();
if (!entryBlock)
return nullptr;
return entryBlock->getLastParam();
}
IRInstList<IRParam> IRGlobalValueWithParams::getParams()
{
auto entryBlock = getFirstBlock();
if (!entryBlock)
return IRInstList<IRParam>();
return entryBlock->getParams();
}
IRInst* IRGlobalValueWithParams::getFirstOrdinaryInst()
{
auto firstBlock = getFirstBlock();
if (!firstBlock)
return nullptr;
return firstBlock->getFirstOrdinaryInst();
}
// IRFunc
IRType* IRFunc::getResultType()
{
return getDataType()->getResultType();
}
UInt IRFunc::getParamCount()
{
return getDataType()->getParamCount();
}
IRType* IRFunc::getParamType(UInt index)
{
return getDataType()->getParamType(index);
}
void fixUpFuncType(IRFunc* func, IRType* resultType)
{
SLANG_ASSERT(func);
auto irModule = func->getModule();
SLANG_ASSERT(irModule);
IRBuilder builder(irModule);
builder.setInsertBefore(func);
List<IRType*> paramTypes;
for (auto param : func->getParams())
{
paramTypes.add(param->getFullType());
}
auto funcType = builder.getFuncType(paramTypes, resultType);
builder.setDataType(func, funcType);
}
void fixUpFuncType(IRFunc* func)
{
fixUpFuncType(func, func->getResultType());
}
//
bool isTerminatorInst(IROp op)
{
switch (op)
{
default:
return false;
case kIROp_Return:
case kIROp_UnconditionalBranch:
case kIROp_ConditionalBranch:
case kIROp_Loop:
case kIROp_IfElse:
case kIROp_Switch:
case kIROp_Unreachable:
case kIROp_MissingReturn:
case kIROp_Defer:
return true;
}
}
bool isTerminatorInst(IRInst* inst)
{
if (!inst)
return false;
return isTerminatorInst(inst->getOp());
}
//
// IRTypeLayout
//
IRTypeSizeAttr* IRTypeLayout::findSizeAttr(LayoutResourceKind kind)
{
// TODO: If we could assume the attributes were sorted
// by `kind`, then we could use a binary search here
// instead of linear.
//
// In practice, the number of entries will be very small,
// so the cost of the linear search should not be too bad.
for (auto sizeAttr : getSizeAttrs())
{
if (sizeAttr->getResourceKind() == kind)
return sizeAttr;
}
return nullptr;
}
IRTypeLayout* IRTypeLayout::unwrapArray()
{
auto typeLayout = this;
while (auto arrayTypeLayout = as<IRArrayTypeLayout>(typeLayout))
typeLayout = arrayTypeLayout->getElementTypeLayout();
return typeLayout;
}
IRTypeLayout* IRTypeLayout::getPendingDataTypeLayout()
{
if (auto attr = findAttr<IRPendingLayoutAttr>())
return cast<IRTypeLayout>(attr->getLayout());
return nullptr;
}
IROperandList<IRTypeSizeAttr> IRTypeLayout::getSizeAttrs()
{
return findAttrs<IRTypeSizeAttr>();
}
IRTypeLayout::Builder::Builder(IRBuilder* irBuilder)
: m_irBuilder(irBuilder)
{
}
void IRTypeLayout::Builder::addResourceUsage(LayoutResourceKind kind, LayoutSize size)
{
auto& resInfo = m_resInfos[Int(kind)];
resInfo.kind = kind;
resInfo.size += size;
}
void IRTypeLayout::Builder::addResourceUsage(IRTypeSizeAttr* sizeAttr)
{
addResourceUsage(sizeAttr->getResourceKind(), sizeAttr->getSize());
}
void IRTypeLayout::Builder::addResourceUsageFrom(IRTypeLayout* typeLayout)
{
for (auto sizeAttr : typeLayout->getSizeAttrs())
{
addResourceUsage(sizeAttr);
}
}
IRTypeLayout* IRTypeLayout::Builder::build()
{
IRBuilder* irBuilder = getIRBuilder();
List<IRInst*> operands;
addOperands(operands);
addAttrs(operands);
return irBuilder->getTypeLayout(getOp(), operands);
}
void IRTypeLayout::Builder::addOperands(List<IRInst*>& operands)
{
addOperandsImpl(operands);
}
void IRTypeLayout::Builder::addAttrs(List<IRInst*>& operands)
{
auto irBuilder = getIRBuilder();
for (auto resInfo : m_resInfos)
{
if (resInfo.kind == LayoutResourceKind::None)
continue;
IRInst* sizeAttr = irBuilder->getTypeSizeAttr(resInfo.kind, resInfo.size);
operands.add(sizeAttr);
}
if (auto pendingTypeLayout = m_pendingTypeLayout)
{
operands.add(irBuilder->getPendingLayoutAttr(pendingTypeLayout));
}
addAttrsImpl(operands);
}
//
// IRParameterGroupTypeLayout
//
void IRParameterGroupTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
ioOperands.add(m_containerVarLayout);
ioOperands.add(m_elementVarLayout);
ioOperands.add(m_offsetElementTypeLayout);
}
IRParameterGroupTypeLayout* IRParameterGroupTypeLayout::Builder::build()
{
return cast<IRParameterGroupTypeLayout>(Super::Builder::build());
}
//
// IRStructTypeLayout
//
void IRStructTypeLayout::Builder::addAttrsImpl(List<IRInst*>& ioOperands)
{
auto irBuilder = getIRBuilder();
for (auto field : m_fields)
{
ioOperands.add(irBuilder->getFieldLayoutAttr(field.key, field.layout));
}
}
//
// IRTupleTypeLayout
//
void IRTupleTypeLayout::Builder::addAttrsImpl(List<IRInst*>& ioOperands)
{
auto irBuilder = getIRBuilder();
for (auto field : m_fields)
{
ioOperands.add(irBuilder->getTupleFieldLayoutAttr(field.layout));
}
}
//
// IRArrayTypeLayout
//
void IRArrayTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
ioOperands.add(m_elementTypeLayout);
}
//
// IRStructuredBufferTypeLayout
//
void IRStructuredBufferTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
ioOperands.add(m_elementTypeLayout);
}
//
// IRPointerTypeLayout
//
void IRPointerTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
SLANG_UNUSED(ioOperands);
// TODO(JS): For now we don't store the value types layout to avoid
// infinite recursion.
// ioOperands.add(m_valueTypeLayout);
}
//
// IRStreamOutputTypeLayout
//
void IRStreamOutputTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
ioOperands.add(m_elementTypeLayout);
}
//
// IRMatrixTypeLayout
//
IRMatrixTypeLayout::Builder::Builder(IRBuilder* irBuilder, MatrixLayoutMode mode)
: Super::Builder(irBuilder)
{
m_modeInst = irBuilder->getIntValue(irBuilder->getIntType(), IRIntegerValue(mode));
}
void IRMatrixTypeLayout::Builder::addOperandsImpl(List<IRInst*>& ioOperands)
{
ioOperands.add(m_modeInst);
}
//
// IRVarLayout
//
bool IRVarLayout::usesResourceKind(LayoutResourceKind kind)
{
// TODO: basing this check on whether or not the
// var layout has an entry for `kind` means that
// we can't just optimize away any entry where
// the offset is zero (which might be a small
// but nice optimization). We could consider shifting
// this test to use the entries on the type layout
// instead (since non-zero resource consumption
// should be an equivalent test).
return findOffsetAttr(kind) != nullptr;
}
bool IRVarLayout::usesResourceFromKinds(LayoutResourceKindFlags kindFlags)
{
// Like usesResourceKind this works because there is an offset stored even if it's 0.
if (kindFlags)
{
for (auto offsetAttr : getOffsetAttrs())
{
if (LayoutResourceKindFlag::make(offsetAttr->getResourceKind()) & kindFlags)
return true;
}
}
return false;
}
IRSystemValueSemanticAttr* IRVarLayout::findSystemValueSemanticAttr()
{
return findAttr<IRSystemValueSemanticAttr>();
}
IRVarOffsetAttr* IRVarLayout::findOffsetAttr(LayoutResourceKind kind)
{
for (auto offsetAttr : getOffsetAttrs())
{
if (offsetAttr->getResourceKind() == kind)
return offsetAttr;
}
return nullptr;
}
IROperandList<IRVarOffsetAttr> IRVarLayout::getOffsetAttrs()
{
return findAttrs<IRVarOffsetAttr>();
}
Stage IRVarLayout::getStage()
{
if (auto stageAttr = findAttr<IRStageAttr>())
return stageAttr->getStage();
return Stage::Unknown;
}
IRVarLayout* IRVarLayout::getPendingVarLayout()
{
if (auto pendingLayoutAttr = findAttr<IRPendingLayoutAttr>())
{
return cast<IRVarLayout>(pendingLayoutAttr->getLayout());
}
return nullptr;
}
IRVarLayout::Builder::Builder(IRBuilder* irBuilder, IRTypeLayout* typeLayout)
: m_irBuilder(irBuilder), m_typeLayout(typeLayout)
{
}
bool IRVarLayout::Builder::usesResourceKind(LayoutResourceKind kind)
{
return m_resInfos[Int(kind)].kind != LayoutResourceKind::None;
}
IRVarLayout::Builder::ResInfo* IRVarLayout::Builder::findOrAddResourceInfo(LayoutResourceKind kind)
{
auto& resInfo = m_resInfos[Int(kind)];
resInfo.kind = kind;
return &resInfo;
}
void IRVarLayout::Builder::setSystemValueSemantic(String const& name, UInt index)
{
m_systemValueSemantic = getIRBuilder()->getSystemValueSemanticAttr(name, index);
}
void IRVarLayout::Builder::setUserSemantic(String const& name, UInt index)
{
m_userSemantic = getIRBuilder()->getUserSemanticAttr(name, index);
}
void IRVarLayout::Builder::setStage(Stage stage)
{
m_stageAttr = getIRBuilder()->getStageAttr(stage);
}
void IRVarLayout::Builder::cloneEverythingButOffsetsFrom(IRVarLayout* that)
{
if (auto systemValueSemantic = that->findAttr<IRSystemValueSemanticAttr>())
m_systemValueSemantic = systemValueSemantic;
if (auto userSemantic = that->findAttr<IRUserSemanticAttr>())
m_userSemantic = userSemantic;
if (auto stageAttr = that->findAttr<IRStageAttr>())
m_stageAttr = stageAttr;
}
IRVarLayout* IRVarLayout::Builder::build()
{
SLANG_ASSERT(m_typeLayout);
IRBuilder* irBuilder = getIRBuilder();
List<IRInst*> operands;
operands.add(m_typeLayout);
for (auto resInfo : m_resInfos)
{
if (resInfo.kind == LayoutResourceKind::None)
continue;
IRInst* varOffsetAttr =
irBuilder->getVarOffsetAttr(resInfo.kind, resInfo.offset, resInfo.space);
operands.add(varOffsetAttr);
}
if (auto semanticAttr = m_userSemantic)
operands.add(semanticAttr);
if (auto semanticAttr = m_systemValueSemantic)
operands.add(semanticAttr);
if (auto stageAttr = m_stageAttr)
operands.add(stageAttr);
if (auto pendingVarLayout = m_pendingVarLayout)
{
IRInst* pendingLayoutAttr = irBuilder->getPendingLayoutAttr(pendingVarLayout);
operands.add(pendingLayoutAttr);
}
return irBuilder->getVarLayout(operands);
}
//
// IREntryPointLayout
//
IRStructTypeLayout* getScopeStructLayout(IREntryPointLayout* scopeLayout)
{
auto scopeTypeLayout = scopeLayout->getParamsLayout()->getTypeLayout();
if (auto constantBufferTypeLayout = as<IRParameterGroupTypeLayout>(scopeTypeLayout))
{
scopeTypeLayout = constantBufferTypeLayout->getOffsetElementTypeLayout();
}
if (auto structTypeLayout = as<IRStructTypeLayout>(scopeTypeLayout))
{
return structTypeLayout;
}
SLANG_UNEXPECTED("uhandled global-scope binding layout");
UNREACHABLE_RETURN(nullptr);
}
//
IRInst* IRInsertLoc::getParent() const
{
auto inst = getInst();
switch (getMode())
{
default:
case Mode::None:
return nullptr;
case Mode::Before:
case Mode::After:
return inst->getParent();
case Mode::AtStart:
case Mode::AtEnd:
return inst;
}
}
IRBlock* IRInsertLoc::getBlock() const
{
return as<IRBlock>(getParent());
}
// Get the current function (or other value with code)
// that we are inserting into (if any).
IRInst* IRInsertLoc::getFunc() const
{
auto pp = getParent();
if (const auto block = as<IRBlock>(pp))
{
pp = pp->getParent();
}
if (as<IRGlobalValueWithCode>(pp) || as<IRExpand>(pp))
return pp;
return nullptr;
}
void addHoistableInst(IRBuilder* builder, IRInst* inst);
// Add an instruction into the current scope
void IRBuilder::addInst(IRInst* inst)
{
if (getIROpInfo(inst->getOp()).isGlobal())
{
addHoistableInst(this, inst);
return;
}
if (!inst->parent)
inst->insertAt(m_insertLoc);
}
IRInst* IRBuilder::replaceOperand(IRUse* use, IRInst* newValue)
{
auto user = use->getUser();
if (user->getModule())
{
user->getModule()->getDeduplicationContext()->getInstReplacementMap().tryGetValue(
newValue,
newValue);
}
if (!getIROpInfo(user->getOp()).isHoistable())
{
use->set(newValue);
return user;
}
// If user is hoistable, we need to remove it from the global number map first,
// perform the update, then try to reinsert it back to the global number map.
// If we find an equivalent entry already exists in the global number map,
// we return the existing entry.
auto builder = user->getModule()->getDeduplicationContext();
builder->_removeGlobalNumberingEntry(user);
use->init(user, newValue);
IRInst* existingVal = nullptr;
if (builder->getGlobalValueNumberingMap().tryGetValue(IRInstKey{user}, existingVal))
{
user->replaceUsesWith(existingVal);
return existingVal;
}
else
{
builder->_addGlobalNumberingEntry(user);
return user;
}
}
// Given two parent instructions, pick the better one to use as as
// insertion location for a "hoistable" instruction.
//
IRInst* mergeCandidateParentsForHoistableInst(IRInst* left, IRInst* right)
{
// If the candidates are both the same, then who cares?
if (left == right)
return left;
// If either `left` or `right` is a block, then we need to be
// a bit careful, because blocks can see other values just using
// the dominance relationship, without a direct parent-child relationship.
//
// First, check if each of `left` and `right` is a block.
//
auto leftBlock = as<IRBlock>(left);
auto rightBlock = as<IRBlock>(right);
//
// As a special case, if both of these are blocks in the same parent,
// then we need to pick between them based on dominance.
//
if (leftBlock && rightBlock && (leftBlock->getParent() == rightBlock->getParent()))
{
// We assume that the order of basic blocks in a function is compatible
// with the dominance relationship (that is, if A dominates B, then
// A comes before B in the list of blocks), so it suffices to pick
// the *later* of the two blocks.
//
// There are ways we could try to speed up this search, but no matter
// what it will be O(n) in the number of blocks, unless we build
// an explicit dominator tree, which is infeasible during IR building.
// Thus we just do a simple linear walk here.
//
// We will start at `leftBlock` and walk forward, until either...
//
for (auto ll = leftBlock; ll; ll = ll->getNextBlock())
{
// ... we see `rightBlock` (in which case `rightBlock` came later), or ...
//
if (ll == rightBlock)
return rightBlock;
}
//
// ... we run out of blocks (in which case `leftBlock` came later).
//
return leftBlock;
}
//
// If the special case above doesn't apply, then `left` or `right` might
// still be a block, but they aren't blocks nested in the same function.
// We will find the first non-block ancestor of `left` and/or `right`.
// This will either be the inst itself (it is isn't a block), or
// its immediate parent (if it *is* a block).
//
auto leftNonBlock = leftBlock ? leftBlock->getParent() : left;
auto rightNonBlock = rightBlock ? rightBlock->getParent() : right;
// If either side is null, then take the non-null one.
//
if (!leftNonBlock)
return right;
if (!rightNonBlock)
return left;
// If the non-block on the left or right is a descendent of
// the other, then that is what we should use.
//
IRInst* parentNonBlock = nullptr;
for (auto ll = leftNonBlock; ll; ll = ll->getParent())
{
if (ll == rightNonBlock)
{
parentNonBlock = leftNonBlock;
break;
}
}
for (auto rr = rightNonBlock; rr; rr = rr->getParent())
{
if (rr == leftNonBlock)
{
SLANG_ASSERT(!parentNonBlock || parentNonBlock == leftNonBlock);
parentNonBlock = rightNonBlock;
break;
}
}
// As a matter of validity in the IR, we expect one
// of the two to be an ancestor (in the non-block case),
// because otherwise we'd be violating the basic dominance
// assumptions.
//
SLANG_ASSERT(parentNonBlock);
// As a fallback, try to use the left parent as a default
// in case things go badly.
//
if (!parentNonBlock)
{
parentNonBlock = leftNonBlock;
}
IRInst* parent = parentNonBlock;
// At this point we've found a non-block parent where we
// could stick things, but we have to fix things up in
// case we should be inserting into a block beneath
// that non-block parent.
if (leftBlock && (parentNonBlock == leftNonBlock))
{
// We have a left block, and have picked its parent.
// It cannot be the case that there is a right block
// with the same parent, or else our special case
// would have triggered at the start.
SLANG_ASSERT(!rightBlock || (parentNonBlock != rightNonBlock));
parent = leftBlock;
}
else if (rightBlock && (parentNonBlock == rightNonBlock))
{
// We have a right block, and have picked its parent.
// We already tested above, so we know there isn't a
// matching situation on the left side.
parent = rightBlock;
}
// Okay, we've picked the parent we want to insert into,
// *but* one last special case arises, because an `IRGlobalValueWithCode`
// is not actually a suitable place to insert instructions.
// Furthermore, there is no actual need to insert instructions at
// that scope, because any parameters, etc. are actually attached
// to the block(s) within the function.
if (auto parentFunc = as<IRGlobalValueWithCode>(parent))
{
// Insert in the parent of the function (or other value with code).
// We know that the parent must be able to hold ordinary instructions,
// because it was able to hold this `IRGlobalValueWithCode`
parent = parentFunc->getParent();
}
return parent;
}
IRInst* IRModule::_allocateInst(IROp op, Int operandCount, size_t minSizeInBytes)
{
// There are two basic cases for instructions that affect how we compute size:
//
// * The default case is that an instruction's state is fully defined by the fields
// in the `IRInst` base type, along with the trailing operand list (a tail-allocated
// array of `IRUse`s. Almost all instructions need space allocated this way.
//
// * A small number of cases (currently `IRConstant`s and the `IRModule` type) have
// *zero* operands but include additional state beyond the fields in `IRInst`.
// For these cases we want to ensure that at least `sizeof(T)` bytes are allocated,
// based on the specific leaf type `T`.
//
// We handle the combination of the two cases by just taking the maximum of the two
// different sizes.
//
size_t defaultSize = sizeof(IRInst) + (operandCount) * sizeof(IRUse);
size_t totalSize = minSizeInBytes > defaultSize ? minSizeInBytes : defaultSize;
IRInst* inst = (IRInst*)m_memoryArena.allocateAndZero(totalSize);
// TODO: Is it actually important to run a constructor here?
new (inst) IRInst();
inst->operandCount = uint32_t(operandCount);
inst->m_op = op;
return inst;
}
/// Return whichever of `left` or `right` represents the later point in a common parent
static IRInst* pickLaterInstInSameParent(IRInst* left, IRInst* right)
{
// When using instructions to represent insertion locations,
// a null instruction represents the end of the parent block,
// so if either of the two instructions is null, it indicates
// the end of the parent, and thus comes later.
//
if (!left)
return nullptr;
if (!right)
return nullptr;
// In the non-null case, we must have the precondition that
// the two candidates have the same parent.
//
SLANG_ASSERT(left->getParent() == right->getParent());
// No matter what, figuring out which instruction comes first
// is a linear-time operation in the number of instructions
// in the same parent, but we can optimize based on the
// assumption that in common cases one of the following will
// hold:
//
// * `left` and `right` are close to one another in the IR
// * `left` and/or `right` is close to the start of its parent
//
// To optimize for those conditions, we create two cursors that
// start at `left` and `right` respectively, and scan backward.
//
auto ll = left;
auto rr = right;
for (;;)
{
// If one of the cursors runs into the other while scanning
// backwards, then it implies it must have been the later
// of the two.
//
// This is our early-exit condition for `left` and `right`
// being close together.
//
// Note: this condition will trigger on the first iteration
// in the case where `left == right`.
//
if (ll == right)
return left;
if (rr == left)
return right;
// If one of the cursors reaches the start of the block,
// then that implies it started at the earlier position.
// In that case, the other candidate must be the later
// one.
//
// This is the early-exit condition for `left` and/or `right`
// being close to the start of the parent.
//
if (!ll)
return right;
if (!rr)
return left;
// Otherwise, we move both cursors backward and continue
// the search.
//
ll = ll->getPrevInst();
rr = rr->getPrevInst();
// Note: in the worst case, one of the cursors is
// at the end of the parent, and the other is halfway
// through, so that each cursor needs to visit half
// of the instructions in the parent before we reach
// one of our termination conditions.
//
// As a result the worst-case running time is still O(N),
// and there is nothing we can do to improve that
// with our linked-list representation.
//
// If the assumptions given turn out to be wrong, and
// we find that a common case is instructions close
// to the *end* of a block, we can either flip the
// direction that the cursors traverse, or even add
// two more cursors that scan forward instead of
// backward.
}
}
// Given an instruction that represents a constant, a type, etc.
// Try to "hoist" it as far toward the global scope as possible
// to insert it at a location where it will be maximally visible.
//
void addHoistableInst(IRBuilder* builder, IRInst* inst)
{
// Start with the assumption that we would insert this instruction
// into the global scope (the instruction that represents the module)
IRInst* parent = builder->getModule()->getModuleInst();
// The above decision might be invalid, because there might be
// one or more operands of the instruction that are defined in
// more deeply nested parents than the global scope.
//
// Therefore, we will scan the operands of the instruction, and
// look at the parents that define them.
//
UInt operandCount = inst->getOperandCount();
for (UInt ii = 0; ii < operandCount; ++ii)
{
auto operand = inst->getOperand(ii);
if (!operand)
continue;
auto operandParent = operand->getParent();
parent = mergeCandidateParentsForHoistableInst(parent, operandParent);
}
if (inst->getFullType())
{
parent = mergeCandidateParentsForHoistableInst(parent, inst->getFullType()->getParent());
}
// We better have ended up with a parent to insert into,
// or else the invariants of our IR have been violated.
//
SLANG_ASSERT(parent);
// Once we determine the parent instruction that the
// new instruction should be inserted into, we need
// to find an appropriate place to insert it.
//
// There are two concerns at play here, both of which
// stem from the property that within a block we
// require definitions to precede their uses.
//
// The first concern is that we want to emit a
// "hoistable" instruction like a type as early as possible,
// so that if a subsequent optimization pass requests
// the same type/value again, it doesn't get a cached/deduplicated
// pointer to an instruction that comes after the code being
// processed.
//
// The second concern is that we must emit any hoistable
// instruction after any of its operands (or its type)
// if they come from the same block/parent.
//
// These two conditions together indicate that we want
// to insert the instruction right after whichever of
// its operands come last in the parent block and if
// none of the operands come from the same block, we
// should try to insert it as early as possible in
// that block.
//
// We want to insert a hoistable instruction at the
// earliest possible point in its parent, which
// should be right after whichever of its operands
// is defined in that same block (if any)
//
// We will solve this problem by computing the
// earliest instruction that it would be valid for
// us to insert before.
//
// We start by considering insertion before the
// first instruction in the parent (if any) and
// then move the insertion point later as needed.
//
// Note: a null `insertBeforeInst` is used
// here to mean to insert at the end of the parent.
//
IRInst* insertBeforeInst = parent->getFirstChild();
// Hoistable instructions are always "ordinary"
// instructions, so they need to come after
// any parameters of the parent.
//
while (insertBeforeInst && insertBeforeInst->getOp() == kIROp_Param)
{
insertBeforeInst = insertBeforeInst->getNextInst();
}
// For instructions that will be placed at module scope,
// we don't care about relative ordering, but for everything
// else, we want to ensure that an instruction comes after
// its type and operands.
//
if (!as<IRModuleInst>(parent))
{
// We need to make sure that if any of
// the operands of `inst` come from the same
// block that we insert after them.
//
for (UInt ii = 0; ii < operandCount; ++ii)
{
auto operand = inst->getOperand(ii);
if (!operand)
continue;
if (operand->getParent() != parent)
continue;
insertBeforeInst = pickLaterInstInSameParent(insertBeforeInst, operand->getNextInst());
}
//
// Similarly, if the type of `inst` comes from
// the same parent, then we need to make sure
// we insert after the type.
//
if (auto type = inst->getFullType())
{
if (type->getParent() == parent)
{
insertBeforeInst = pickLaterInstInSameParent(insertBeforeInst, type->getNextInst());
}
}
}
if (insertBeforeInst)
{
inst->insertBefore(insertBeforeInst);
}
else
{
inst->insertAtEnd(parent);
}
}
void IRBuilder::_maybeSetSourceLoc(IRInst* inst)
{
auto sourceLocInfo = getSourceLocInfo();
if (!sourceLocInfo)
return;
// Try to find something with usable location info
for (;;)
{
if (sourceLocInfo->sourceLoc.getRaw())
break;
if (!sourceLocInfo->next)
break;
sourceLocInfo = sourceLocInfo->next;
}
inst->sourceLoc = sourceLocInfo->sourceLoc;
}
#if SLANG_ENABLE_IR_BREAK_ALLOC
uint32_t _slangIRAllocBreak = 0xFFFFFFFF;
bool _slangIRPrintStackAtBreak = false;
static bool _slangIRAllocBreakFirst = true;
static uint32_t _slangInstBeingCloned = 0xFFFFFFFF;
void _debugSetInstBeingCloned(uint32_t uid)
{
_slangInstBeingCloned = uid;
}
void _debugResetInstBeingCloned()
{
_slangInstBeingCloned = 0xFFFFFFFF;
}
uint32_t& _debugGetIRAllocCounter()
{
static uint32_t counter = 0;
return counter;
}
uint32_t _debugGetAndIncreaseInstCounter()
{
if (_slangIRAllocBreakFirst)
{
// You can set a breakpoint here to break on the first allocation
_slangIRAllocBreakFirst = false;
}
if (_slangIRAllocBreak != 0xFFFFFFFF && _debugGetIRAllocCounter() == _slangIRAllocBreak)
{
#if _WIN32 && defined(_MSC_VER)
__debugbreak();
#endif
if (_slangIRPrintStackAtBreak)
{
fprintf(stdout, "BEGIN IR Trace\nInstruction #%u created at:\n", _slangIRAllocBreak);
PlatformUtil::backtrace();
if (_slangInstBeingCloned != 0xFFFFFFFF)
{
fprintf(
stdout,
"Inst #%u is a clone of Inst #%u.\n",
_slangIRAllocBreak,
_slangInstBeingCloned);
}
fprintf(stdout, "END IR Trace\n");
}
}
return _debugGetIRAllocCounter()++;
}
#endif
IRInst* IRBuilder::_createInst(
size_t minSizeInBytes,
IRType* type,
IROp op,
Int fixedArgCount,
IRInst* const* fixedArgs,
|