chromium/third_party/spirv-tools/src/source/opt/merge_return_pass.h

// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SOURCE_OPT_MERGE_RETURN_PASS_H_
#define SOURCE_OPT_MERGE_RETURN_PASS_H_

#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "source/opt/basic_block.h"
#include "source/opt/function.h"
#include "source/opt/mem_pass.h"

namespace spvtools {
namespace opt {

/*******************************************************************************
 *
 * Handling Structured Control Flow:
 *
 * Structured control flow guarantees that the CFG will converge at a given
 * point (the merge block). Within structured control flow, all blocks must be
 * post-dominated by the merge block, except return blocks and break blocks.
 * A break block is a block that branches to a containing construct's merge
 * block.
 *
 * Beyond this, we further assume that all unreachable blocks have been
 * cleaned up.  This means that the only unreachable blocks are those necessary
 * for valid structured control flow.
 *
 * Algorithm:
 *
 * If a return is encountered, it should record that: i) the function has
 * "returned" and ii) the value of the return. The return should be replaced
 * with a branch. If current block is not within structured control flow, this
 * is the final return. This block should branch to the new return block (its
 * direct successor). If the current block is within structured control flow,
 * the branch destination should be the innermost construct's merge.  This
 * merge will always exist because a single case switch is added around the
 * entire function. If the merge block produces any live values it will need to
 * be predicated. While the merge is nested in structured control flow, the
 * predication path should branch to the merge block of the inner-most loop
 * (or switch if no loop) it is contained in. Once structured control flow has
 * been exited, it will be at the merge of the single case switch, which will
 * simply return.
 *
 * In the final return block, the return value should be loaded and returned.
 * Memory promotion passes should be able to promote the newly introduced
 * variables ("has returned" and "return value").
 *
 * Predicating the Final Merge:
 *
 * At each merge block predication needs to be introduced (optimization: only if
 * that block produces value live beyond it). This needs to be done carefully.
 * The merge block should be split into multiple blocks.
 *
 *          1 (loop header)
 *        /   \
 * (ret) 2     3 (merge)
 *
 *         ||
 *         \/
 *
 *          0 (single case switch header)
 *          |
 *          1 (loop header)
 *         / \
 *        2  | (merge)
 *        \ /
 *         3' (merge)
 *        / \
 *        |  3 (original code in 3)
 *        \ /
 *   (ret) 4 (single case switch merge)
 *
 * In the above (simple) example, the return originally in |2| is passed through
 * the loop merge. That merge is predicated such that the old body of the block
 * is the else branch. The branch condition is based on the value of the "has
 * returned" variable.
 *
 ******************************************************************************/

// Documented in optimizer.hpp
class MergeReturnPass : public MemPass { … };

}  // namespace opt
}  // namespace spvtools

#endif  // SOURCE_OPT_MERGE_RETURN_PASS_H_