From 6cbc3929a54d37bd23cb5efa8e3320ba02f78b2f Mon Sep 17 00:00:00 2001 From: jsmall-nvidia Date: Fri, 31 May 2019 17:20:37 -0400 Subject: Use slang- prefix on slang compiler and core source (#973) * Prefixing source files in source/slang with slang- * Prefix source in source/slang with slang- prefix. * Rename core source files with slang- prefix. * Update project files. * Fix problems from automatic merge. --- source/slang/ir-restructure-scoping.cpp | 434 -------------------------------- 1 file changed, 434 deletions(-) delete mode 100644 source/slang/ir-restructure-scoping.cpp (limited to 'source/slang/ir-restructure-scoping.cpp') diff --git a/source/slang/ir-restructure-scoping.cpp b/source/slang/ir-restructure-scoping.cpp deleted file mode 100644 index c5e628e71..000000000 --- a/source/slang/ir-restructure-scoping.cpp +++ /dev/null @@ -1,434 +0,0 @@ -// ir-restructure-scoping.cpp -#include "ir-restructure-scoping.h" - -#include "ir.h" -#include "ir-insts.h" -#include "ir-restructure.h" - -namespace Slang -{ - -/// Try to find the first structured region that represents `block` -/// -/// In general the same block may appear as multiple regions, -/// so this will return the first region in the linked list. -static SimpleRegion* getFirstRegionForBlock( - RegionTree* regionTree, - IRBlock* block) -{ - SimpleRegion* region = nullptr; - if( regionTree->mapBlockToRegion.TryGetValue(block, region) ) - { - return region; - } - return nullptr; -} - -/// Try to find the first structured region that contains `inst`. -static SimpleRegion* getFirstRegionForInst( - RegionTree* regionTree, - IRInst* inst) -{ - auto ii = inst; - while(ii) - { - if(auto block = as(ii)) - return getFirstRegionForBlock(regionTree, block); - - ii = ii->getParent(); - } - - return nullptr; -} - -/// Compute the depth of a node in the region tree. -/// -/// This is the number of nodes (including `region`) -/// on a path from `region` to the root. -/// -static Int computeDepth(Region* region) -{ - Int depth = 0; - for( Region* rr = region; rr; rr = rr->getParent() ) - { - depth++; - } - return depth; -} - -/// Get the `n`th ancestor of `region`. -/// -/// When `n` is zero, this returns `region`. -/// When `n` is one, this returns the parent of `region`, and so forth. -/// -static Region* getAncestor(Region* region, Int n) -{ - Region* rr = region; - for( Int ii = 0; ii < n; ++ii ) - { - SLANG_ASSERT(rr); - rr = rr->getParent(); - } - return rr; -} - -/// Find a region that is an ancestor of both `left` and `right`. -static Region* findCommonAncestorRegion( - Region* left, - Region* right) -{ - // Rather than blinding search through each ancestor of `left` - // and see if it is also an ancestor of `right` and vice-versa, - // let's try to be smart about this. - // - // We will start by computing the depth of `left` and `right`: - // - Int leftDepth = computeDepth(left); - Int rightDepth = computeDepth(right); - - // Whatever the common ancestor is, it can't be any deeper - // than the minimum of these two depths. - // - Int minDepth = Math::Min(leftDepth, rightDepth); - - // Let's fetch the ancestor of each of `left` and `right` - // corresponding to that depth: - // - Region* leftAncestor = getAncestor(left, leftDepth - minDepth); - Region* rightAncestor = getAncestor(right, rightDepth - minDepth); - - // Now we know that `leftAncestor` and `rightAncestor` - // must have the same depth. Let's go ahead and assert - // it just to be safe: - // - SLANG_ASSERT(computeDepth(leftAncestor) == minDepth); - SLANG_ASSERT(computeDepth(rightAncestor) == minDepth); - - // If `leftAncestor` and `rightAncestor` are the same node, - // then we've found a common ancestor, otherwise we should - // look at their parents. Because the depth must match - // on both sides, we will never risk missing an ancestor. - // - while( leftAncestor != rightAncestor ) - { - leftAncestor = leftAncestor->getParent(); - rightAncestor = rightAncestor->getParent(); - } - - // Okay, we've found a common ancestor. - // - Region* commonAncestor = leftAncestor; - return commonAncestor; -} - -/// Find a simple region that is an ancestor of both `left` and `right`. -static SimpleRegion* findSimpleCommonAncestorRegion( - Region* left, - Region* right) -{ - // Start by finding a common ancestor without worrying about it being simple. - Region* ancestor = findCommonAncestorRegion(left, right); - - // Now search for a simple region up the tree. - while( ancestor ) - { - if(ancestor->getFlavor() == Region::Flavor::Simple) - return (SimpleRegion*) ancestor; - - ancestor = ancestor->getParent(); - } - - // This shouldn't ever occur. The root of the region tree should - // be a simple regions that represents the entry block of the - // function. - // - SLANG_UNEXPECTED("no common ancestor found in region tree"); - UNREACHABLE_RETURN(nullptr); -} - -IRInst* getDefaultInitVal( - IRBuilder* builder, - IRType* type) -{ - switch( type->op ) - { - default: - return nullptr; - - case kIROp_BoolType: - return builder->getBoolValue(false); - - case kIROp_IntType: - case kIROp_UIntType: - case kIROp_UInt64Type: - return builder->getIntValue(type, 0); - - case kIROp_HalfType: - case kIROp_FloatType: - case kIROp_DoubleType: - return builder->getFloatValue(type, 0.0); - - // TODO: handle vector/matrix types here, by - // creating an appropriate scalar value and - // then "splatting" it. - } -} - -/// Initialize a variable to a sane default value, if possible. -void defaultInitializeVar( - IRBuilder* builder, - IRVar* var, - IRType* type) -{ - IRInst* initVal = nullptr; - switch( type->op ) - { - case kIROp_VoidType: - default: - // By default, see if we can synthesize an IR value - // to be used as the default, and allow the logic - // below to store it into the variable. - initVal = getDefaultInitVal(builder, type); - break; - - // TODO: Handle aggregate types (structures, arrays) - // explicitly here, since they need to be careful about - // the cases where an element/field type might not - // be something we can default-initialize. - } - - if( initVal ) - { - builder->emitStore(var, initVal); - } -} - -/// Detect and fix any structured scoping issues for a given `def` instruction. -/// -/// The `defRegion` should be the region that contains `def`, and `regionTree` -/// should be the region tree for the function that contains `def`. -/// -static void fixValueScopingForInst( - IRInst* def, - SimpleRegion* defRegion, - RegionTree* regionTree) -{ - // This algorithm should not consider "phi nodes" for now, - // because the emit logic will already create variables for them. - // We could consider folding the logic to move out of SSA form - // into this function, but that would add a lot of complexity for now. - if(def->op == kIROp_Param) - return; - - // We would have a scoping violation if there exists some - // use `u` of `def` such that the region containing `u` - // (call it `useRegion`) is not a descendent of `defRegion` - // in the region tree. - // - // If there are no scoping violations, we don't want to do - // anything. If there *are* any scoping violations, then - // we ill need to introduce a temporary `tmp`, store into - // it right after `def`, and then load from it at any "bad" - // use sites. - // - // Of course, for the whole thing to work, we also need - // to put `tmp` into a block somwhere, and it needs to - // be a block that is visible to all of the uses, or we - // are just back int the same mess again. - // - // The right block to use for inserting `tmp` is the least - // common ancestor of `def` and all the "bad" uses, so - // we will get a bit "clever" and fold in the search for - // bad uses with the computation of the region we should - // insert `tmp` into (to avoid looping over the uses - // twice). - // - SimpleRegion* insertRegion = defRegion; - IRVar* tmp = nullptr; - - // If we end up needing to insert code we'll need an IR builder, - // so we will go ahead and create one now. - // - // TODO: the logic to compute `module` here could be hoisted - // out earlier, rather than being done per-instruction. - // - IRModule* module = regionTree->irCode->getModule(); - - SharedIRBuilder sharedBuilder; - sharedBuilder.session = module->session; - sharedBuilder.module = module; - - IRBuilder builder; - builder.sharedBuilder = &sharedBuilder; - - // Because we will be changing some of the uses of `def` - // to use other values while we iterate the list, we - // need to be a bit careful and extract the next use - // in the linked list *before* we operator on `u`. - // - IRUse* nextUse = nullptr; - for( auto u = def->firstUse; u; u = nextUse ) - { - nextUse = u->nextUse; - - // Looking at the use site `u`, we'd like to check if - // it violates our scoping rules. - // - // As a simple early-exit case, if the user is in - // the same block as the definition, there are no problems. - // - IRInst* user = u->getUser(); - if(user->getParent() == defRegion->block) - continue; - - // Otherwise, let's find the structures control-flow - // region that holds the user. We expect to always - // find one, because the use site must be in the same - // function. - // - // TODO: Double check that logic if we ever introduce - // things like nested function. - // - SimpleRegion* useRegion = getFirstRegionForInst(regionTree, user); - - // If there is no region associated with the use, then - // the use must be in unreachable code (part of the CFG, - // but not part of the region tree). We will skip - // such uses for now, since they won't even appear in - // the output. - // - if(!useRegion) - continue; - - // Now we want to check if `useRegion` is a child/descendent - // of a region that has the same block as `defRegion`. - // If it is, then there is no scoping problem with this use. - // - if(useRegion->isDescendentOf(defRegion->block)) - continue; - - // If we've gotten this far, we know that `u` is a "bad" - // use of `def`, and needs fixing. - // - // We will create the `tmp` variable on demand, so - // that we create it when the first "bad" use is encountered, - // and then re-use it for subsequent bad uses. - // - if( !tmp ) - { - // We will create a temporary to represent `def`, - // and insert a `store` into it right after `def`. - // - // Note: we are inserting the new variable right - // after `def` for now, just because we don't - // yet know the final region that it should be - // placed into. We will move it to the correct - // location when we are done. - // - builder.setInsertBefore(def->getNextInst()); - tmp = builder.emitVar(def->getDataType()); - builder.emitStore(tmp, def); - } - - // In order to know where `tmp` should be defined - // at the end of the algorithm, we need to compute - // a valid `insertRegion` that is an ancestor of - // all of the use sites (and it also a simple region - // so that we can insert into its IR block). - // - // We need to deal with one complexity in our restructuring - // process, which is that a block may be duplicated into - // one or more regions, so we loop over all the regions - // for the same block as `useRegion`. - // - for(auto rr = useRegion; rr; rr = rr->nextSimpleRegionForSameBlock) - { - insertRegion = findSimpleCommonAncestorRegion( - insertRegion, - rr); - } - - // To fix up the use `u`, we will need to change - // it from using `def` to using a load from `tmp` - // - builder.setInsertBefore(user); - IRInst* tmpVal = builder.emitLoad(tmp); - - // We are clobbering the value used by the `IRUse` `u`, - // while will cut it out of the list of uses for `def`. - // We need to be careful when doing this to not disrupt - // our iteration of the uses of `def`, so we carefully - // used the `nextUse` temporary at the start of the loop. - // - u->set(tmpVal); - } - - // At the end of the loop, the `tmp` variable will have - // been created if and only if we fixed up anything. - // - if( tmp ) - { - // If we created a temporary, then now we need to move - // its definition to the right place, which is the - // `insertRegion` that we computed during the loop. - // - // We'd like to insert our temporary near the top - // of the region, since that is the conventional - // place for local variables to go. - // - tmp->insertBefore( - insertRegion->block->getFirstOrdinaryInst()); - - // The whole point of the transformation we are doing - // here is that `def` is not on the "obvious" control - // flow path to one or more uses (which are now using - // `tmp`), but that means that it might not be "obvious" - // to a downstream compiler that `tmp` always gets - // initialized (by the code we inserted after `def`) - // before each of these use sites. - // - // We *know* that things are valid as long as our - // dominator tree was valid - there is no way to - // get to the block that loads from `tmp` without passing - // through the block that computes `def` (and then - // stores it into `tmp`) first. - // - // To avoid warnings/errros, we will go ahead and try - // to emit logic to "default initialize" the `tmp` - // variable if possible. - // - builder.setInsertBefore(tmp->getNextInst()); - defaultInitializeVar(&builder, tmp, def->getDataType()); - } -} - -void fixValueScoping(RegionTree* regionTree) -{ - // We are going to have to walk through every instruction - // in the code of the function to detect an bad cases. - // - auto code = regionTree->irCode; - for(auto block : code->getBlocks()) - { - // All of the instruction in `block` will have the same - // parent region, so we will look it up now rather than - // have to re-do this work on a per-instruction basis. - // - auto parentRegion = getFirstRegionForBlock(regionTree, block); - - // If a block has no region then it must be unreachable, - // so we will skip it entirely for this pass. - // - // TODO: we should be eliminating unrechable blocks anyway. - // - if(!parentRegion) - continue; - - for(auto inst : block->getDecorationsAndChildren()) - { - fixValueScopingForInst(inst, parentRegion, regionTree); - } - } -} - -} -- cgit v1.2.3