chromium/third_party/spirv-tools/src/source/cfa.h

// Copyright (c) 2015-2016 The Khronos Group 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_CFA_H_
#define SOURCE_CFA_H_

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace spvtools {

// Control Flow Analysis of control flow graphs of basic block nodes |BB|.
template <class BB>
class CFA { … };

template <class BB>
bool CFA<BB>::FindInWorkList(const std::vector<block_info>& work_list,
                             uint32_t id) { … }

template <class BB>
void CFA<BB>::DepthFirstTraversal(const BB* entry,
                                  get_blocks_func successor_func,
                                  std::function<void(cbb_ptr)> preorder,
                                  std::function<void(cbb_ptr)> postorder,
                                  std::function<bool(cbb_ptr)> terminal) { … }

template <class BB>
void CFA<BB>::DepthFirstTraversal(
    const BB* entry, get_blocks_func successor_func,
    std::function<void(cbb_ptr)> preorder,
    std::function<void(cbb_ptr)> postorder,
    std::function<void(cbb_ptr, cbb_ptr)> backedge,
    std::function<bool(cbb_ptr)> terminal) { … }

template <class BB>
std::vector<std::pair<BB*, BB*>> CFA<BB>::CalculateDominators(
    const std::vector<cbb_ptr>& postorder, get_blocks_func predecessor_func) { … }

template <class BB>
std::vector<BB*> CFA<BB>::TraversalRoots(const std::vector<BB*>& blocks,
                                         get_blocks_func succ_func,
                                         get_blocks_func pred_func) { … }

template <class BB>
void CFA<BB>::ComputeAugmentedCFG(
    std::vector<BB*>& ordered_blocks, BB* pseudo_entry_block,
    BB* pseudo_exit_block,
    std::unordered_map<const BB*, std::vector<BB*>>* augmented_successors_map,
    std::unordered_map<const BB*, std::vector<BB*>>* augmented_predecessors_map,
    get_blocks_func succ_func, get_blocks_func pred_func) { … }

}  // namespace spvtools

#endif  // SOURCE_CFA_H_