//

// Copyright (C) 2016 Google, Inc.

//

// All rights reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions

// are met:

//

//    Redistributions of source code must retain the above copyright

//    notice, this list of conditions and the following disclaimer.

//

//    Redistributions in binary form must reproduce the above

//    copyright notice, this list of conditions and the following

//    disclaimer in the documentation and/or other materials provided

//    with the distribution.

//

//    Neither the name of 3Dlabs Inc. Ltd. nor the names of its

//    contributors may be used to endorse or promote products derived

//    from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER

// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN

// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

// POSSIBILITY OF SUCH DAMAGE.

// The SPIR-V spec requires code blocks to appear in an order satisfying the

// dominator-tree direction (ie, dominator before the dominated).  This is,

// actually, easy to achieve: any pre-order CFG traversal algorithm will do it.

// Because such algorithms visit a block only after traversing some path to it

// from the root, they necessarily visit the block's idom first.

//

// But not every graph-traversal algorithm outputs blocks in an order that

// appears logical to human readers.  The problem is that unrelated branches may

// be interspersed with each other, and merge blocks may come before some of the

// branches being merged.

//

// A good, human-readable order of blocks may be achieved by performing

// depth-first search but delaying merge nodes until after all their branches

// have been visited.  This is implemented below by the inReadableOrder()

// function.

#include "spvIR.h"

#include <cassert>

#include <unordered_set>

using spv::Block;

using spv::Id;

namespace {

// Traverses CFG in a readable order, invoking a pre-set callback on each block.

// Use by calling visit() on the root block.

class ReadableOrderTraverser {

public:

    ReadableOrderTraverser(std::function<void(Block*, spv::ReachReason, Block*)> callback)

      : callback_(callback) {}

    // Visits the block if it hasn't been visited already and isn't currently

    // being delayed.  Invokes callback(block, why, header), then descends into its

    // successors.  Delays merge-block and continue-block processing until all

    // the branches have been completed.  If |block| is an unreachable merge block or

    // an unreachable continue target, then |header| is the corresponding header block.

    void visit(Block* block, spv::ReachReason why, Block* header)

    {

        assert(block);

        if (why == spv::ReachViaControlFlow) {

            reachableViaControlFlow_.insert(block);

        }

        if (visited_.count(block) || delayed_.count(block))

            return;

        callback_(block, why, header);

        visited_.insert(block);

        Block* mergeBlock = nullptr;

        Block* continueBlock = nullptr;

        auto mergeInst = block->getMergeInstruction();

        if (mergeInst) {

            Id mergeId = mergeInst->getIdOperand(0);

            mergeBlock = block->getParent().getParent().getInstruction(mergeId)->getBlock();

            delayed_.insert(mergeBlock);

            if (mergeInst->getOpCode() == spv::Op::OpLoopMerge) {

                Id continueId = mergeInst->getIdOperand(1);

                continueBlock =

                    block->getParent().getParent().getInstruction(continueId)->getBlock();

                delayed_.insert(continueBlock);

            }

        }

        if (why == spv::ReachViaControlFlow) {

            const auto& successors = block->getSuccessors();

            for (auto it = successors.cbegin(); it != successors.cend(); ++it)

                visit(*it, why, nullptr);

        }

        if (continueBlock) {

            const spv::ReachReason continueWhy =

                (reachableViaControlFlow_.count(continueBlock) > 0)

                    ? spv::ReachViaControlFlow

                    : spv::ReachDeadContinue;

            delayed_.erase(continueBlock);

            visit(continueBlock, continueWhy, block);

        }

        if (mergeBlock) {

            const spv::ReachReason mergeWhy =

                (reachableViaControlFlow_.count(mergeBlock) > 0)

                    ? spv::ReachViaControlFlow

                    : spv::ReachDeadMerge;

            delayed_.erase(mergeBlock);

            visit(mergeBlock, mergeWhy, block);

        }

    }

private:

    std::function<void(Block*, spv::ReachReason, Block*)> callback_;

    // Whether a block has already been visited or is being delayed.

    std::unordered_set<Block *> visited_, delayed_;

    // The set of blocks that actually are reached via control flow.

    std::unordered_set<Block *> reachableViaControlFlow_;

};

}

void spv::inReadableOrder(Block* root, std::function<void(Block*, spv::ReachReason, Block*)> callback)

{

    ReadableOrderTraverser(callback).visit(root, spv::ReachViaControlFlow, nullptr);

}