loop_descriptor.cpp | Explore in Territory

// 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.

#include "source/opt/loop_descriptor.h"

#include <algorithm>
#include <limits>
#include <stack>
#include <utility>
#include <vector>

#include "source/opt/cfg.h"
#include "source/opt/constants.h"
#include "source/opt/dominator_tree.h"
#include "source/opt/ir_context.h"
#include "source/opt/iterator.h"
#include "source/opt/tree_iterator.h"
#include "source/util/make_unique.h"

namespace spvtools {
namespace opt {

// Takes in a phi instruction |induction| and the loop |header| and returns the
// step operation of the loop.
Instruction* Loop::GetInductionStepOperation(
    const Instruction* induction) const { … }

// Returns true if the |step| operation is an induction variable step operation
// which is currently handled.
bool Loop::IsSupportedStepOp(spv::Op step) const { … }

bool Loop::IsSupportedCondition(spv::Op condition) const { … }

int64_t Loop::GetResidualConditionValue(spv::Op condition,
                                        int64_t initial_value,
                                        int64_t step_value,
                                        size_t number_of_iterations,
                                        size_t factor) { … }

Instruction* Loop::GetConditionInst() const { … }

// Extract the initial value from the |induction| OpPhi instruction and store it
// in |value|. If the function couldn't find the initial value of |induction|
// return false.
bool Loop::GetInductionInitValue(const Instruction* induction,
                                 int64_t* value) const { … }

Loop::Loop(IRContext* context, DominatorAnalysis* dom_analysis,
           BasicBlock* header, BasicBlock* continue_target,
           BasicBlock* merge_target)
    : … { … }

BasicBlock* Loop::FindLoopPreheader(DominatorAnalysis* dom_analysis) { … }

bool Loop::IsInsideLoop(Instruction* inst) const { … }

bool Loop::IsBasicBlockInLoopSlow(const BasicBlock* bb) { … }

BasicBlock* Loop::GetOrCreatePreHeaderBlock() { … }

void Loop::SetContinueBlock(BasicBlock* continue_block) { … }

void Loop::SetLatchBlock(BasicBlock* latch) { … }

void Loop::SetMergeBlock(BasicBlock* merge) { … }

void Loop::SetPreHeaderBlock(BasicBlock* preheader) { … }

BasicBlock* Loop::FindLatchBlock() { … }

void Loop::GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const { … }

void Loop::GetMergingBlocks(
    std::unordered_set<uint32_t>* merging_blocks) const { … }

namespace {

inline bool IsBasicBlockSafeToClone(IRContext* context, BasicBlock* bb) { … }

}  // namespace

bool Loop::IsSafeToClone() const { … }

bool Loop::IsLCSSA() const { … }

bool Loop::ShouldHoistInstruction(const Instruction& inst) const { … }

bool Loop::AreAllOperandsOutsideLoop(const Instruction& inst) const { … }

void Loop::ComputeLoopStructuredOrder(
    std::vector<BasicBlock*>* ordered_loop_blocks, bool include_pre_header,
    bool include_merge) const { … }

LoopDescriptor::LoopDescriptor(IRContext* context, const Function* f)
    : … { … }

LoopDescriptor::~LoopDescriptor() { … }

void LoopDescriptor::PopulateList(IRContext* context, const Function* f) { … }

std::vector<Loop*> LoopDescriptor::GetLoopsInBinaryLayoutOrder() { … }

BasicBlock* Loop::FindConditionBlock() const { … }

bool Loop::FindNumberOfIterations(const Instruction* induction,
                                  const Instruction* branch_inst,
                                  size_t* iterations_out,
                                  int64_t* step_value_out,
                                  int64_t* init_value_out) const { … }

// We retrieve the number of iterations using the following formula, diff /
// |step_value| where diff is calculated differently according to the
// |condition| and uses the |condition_value| and |init_value|. If diff /
// |step_value| is NOT cleanly divisible then we add one to the sum.
int64_t Loop::GetIterations(spv::Op condition, int64_t condition_value,
                            int64_t init_value, int64_t step_value) const { … }

// Returns the list of induction variables within the loop.
void Loop::GetInductionVariables(
    std::vector<Instruction*>& induction_variables) const { … }

Instruction* Loop::FindConditionVariable(
    const BasicBlock* condition_block) const { … }

bool LoopDescriptor::CreatePreHeaderBlocksIfMissing() { … }

// Add and remove loops which have been marked for addition and removal to
// maintain the state of the loop descriptor class.
void LoopDescriptor::PostModificationCleanup() { … }

void LoopDescriptor::ClearLoops() { … }

// Adds a new loop nest to the descriptor set.
Loop* LoopDescriptor::AddLoopNest(std::unique_ptr<Loop> new_loop) { … }

void LoopDescriptor::RemoveLoop(Loop* loop) { … }

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