loop_utils.cpp | Explore in Territory

// Copyright (c) 2018 Google LLC.
//
// 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.

#include <algorithm>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "source/cfa.h"
#include "source/opt/cfg.h"
#include "source/opt/ir_builder.h"
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"
#include "source/opt/loop_utils.h"

namespace spvtools {
namespace opt {
namespace {
// Return true if |bb| is dominated by at least one block in |exits|
inline bool DominatesAnExit(BasicBlock* bb,
                            const std::unordered_set<BasicBlock*>& exits,
                            const DominatorTree& dom_tree) { … }

// Utility class to rewrite out-of-loop uses of an in-loop definition in terms
// of phi instructions to achieve a LCSSA form.
// For a given definition, the class user registers phi instructions using that
// definition in all loop exit blocks by which the definition escapes.
// Then, when rewriting a use of the definition, the rewriter walks the
// paths from the use the loop exits. At each step, it will insert a phi
// instruction to merge the incoming value according to exit blocks definition.
class LCSSARewriter { … };

// Make the set |blocks| closed SSA. The set is closed SSA if all the uses
// outside the set are phi instructions in exiting basic block set (hold by
// |lcssa_rewriter|).
inline void MakeSetClosedSSA(IRContext* context, Function* function,
                             const std::unordered_set<uint32_t>& blocks,
                             const std::unordered_set<BasicBlock*>& exit_bb,
                             LCSSARewriter* lcssa_rewriter) { … }

}  // namespace

void LoopUtils::CreateLoopDedicatedExits() { … }

void LoopUtils::MakeLoopClosedSSA() { … }

Loop* LoopUtils::CloneLoop(LoopCloningResult* cloning_result) const { … }

Loop* LoopUtils::CloneAndAttachLoopToHeader(LoopCloningResult* cloning_result) { … }

Loop* LoopUtils::CloneLoop(
    LoopCloningResult* cloning_result,
    const std::vector<BasicBlock*>& ordered_loop_blocks) const { … }

void LoopUtils::PopulateLoopNest(
    Loop* new_loop, const LoopCloningResult& cloning_result) const { … }

// Populates |new_loop| descriptor according to |old_loop|'s one.
void LoopUtils::PopulateLoopDesc(
    Loop* new_loop, Loop* old_loop,
    const LoopCloningResult& cloning_result) const { … }

// Class to gather some metrics about a region of interest.
void CodeMetrics::Analyze(const Loop& loop) { … }

}  // namespace opt
}  // namespace spvtools
chromium/third_party/spirv-tools/src/source/opt/loop_utils.cpp
