scalar_analysis.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 "source/opt/scalar_analysis.h"

#include <functional>
#include <string>
#include <utility>

#include "source/opt/ir_context.h"

// Transforms a given scalar operation instruction into a DAG representation.
//
// 1. Take an instruction and traverse its operands until we reach a
// constant node or an instruction which we do not know how to compute the
// value, such as a load.
//
// 2. Create a new node for each instruction traversed and build the nodes for
// the in operands of that instruction as well.
//
// 3. Add the operand nodes as children of the first and hash the node. Use the
// hash to see if the node is already in the cache. We ensure the children are
// always in sorted order so that two nodes with the same children but inserted
// in a different order have the same hash and so that the overloaded operator==
// will return true. If the node is already in the cache return the cached
// version instead.
//
// 4. The created DAG can then be simplified by
// ScalarAnalysis::SimplifyExpression, implemented in
// scalar_analysis_simplification.cpp. See that file for further information on
// the simplification process.
//

namespace spvtools {
namespace opt {

uint32_t SENode::NumberOfNodes = …;

ScalarEvolutionAnalysis::ScalarEvolutionAnalysis(IRContext* context)
    : … { … }

SENode* ScalarEvolutionAnalysis::CreateNegation(SENode* operand) { … }

SENode* ScalarEvolutionAnalysis::CreateConstant(int64_t integer) { … }

SENode* ScalarEvolutionAnalysis::CreateRecurrentExpression(
    const Loop* loop, SENode* offset, SENode* coefficient) { … }

SENode* ScalarEvolutionAnalysis::AnalyzeMultiplyOp(
    const Instruction* multiply) { … }

SENode* ScalarEvolutionAnalysis::CreateMultiplyNode(SENode* operand_1,
                                                    SENode* operand_2) { … }

SENode* ScalarEvolutionAnalysis::CreateSubtraction(SENode* operand_1,
                                                   SENode* operand_2) { … }

SENode* ScalarEvolutionAnalysis::CreateAddNode(SENode* operand_1,
                                               SENode* operand_2) { … }

SENode* ScalarEvolutionAnalysis::AnalyzeInstruction(const Instruction* inst) { … }

SENode* ScalarEvolutionAnalysis::AnalyzeConstant(const Instruction* inst) { … }

// Handles both addition and subtraction. If the |sub| flag is set then the
// addition will be op1+(-op2) otherwise op1+op2.
SENode* ScalarEvolutionAnalysis::AnalyzeAddOp(const Instruction* inst) { … }

SENode* ScalarEvolutionAnalysis::AnalyzePhiInstruction(const Instruction* phi) { … }

SENode* ScalarEvolutionAnalysis::CreateValueUnknownNode(
    const Instruction* inst) { … }

SENode* ScalarEvolutionAnalysis::CreateCantComputeNode() { … }

// Add the created node into the cache of nodes. If it already exists return it.
SENode* ScalarEvolutionAnalysis::GetCachedOrAdd(
    std::unique_ptr<SENode> prospective_node) { … }

bool ScalarEvolutionAnalysis::IsLoopInvariant(const Loop* loop,
                                              const SENode* node) const { … }

SENode* ScalarEvolutionAnalysis::GetCoefficientFromRecurrentTerm(
    SENode* node, const Loop* loop) { … }

SENode* ScalarEvolutionAnalysis::UpdateChildNode(SENode* parent,
                                                 SENode* old_child,
                                                 SENode* new_child) { … }

// Rebuild the |node| eliminating, if it exists, the recurrent term which
// belongs to the |loop|.
SENode* ScalarEvolutionAnalysis::BuildGraphWithoutRecurrentTerm(
    SENode* node, const Loop* loop) { … }

// Return the recurrent term belonging to |loop| if it appears in the graph
// starting at |node| or null if it doesn't.
SERecurrentNode* ScalarEvolutionAnalysis::GetRecurrentTerm(SENode* node,
                                                           const Loop* loop) { … }
std::string SENode::AsString() const { … }

bool SENode::operator==(const SENode& other) const { … }

bool SENode::operator!=(const SENode& other) const { … }

namespace {
// Helper functions to insert 32/64 bit values into the 32 bit hash string. This
// allows us to add pointers to the string by reinterpreting the pointers as
// uintptr_t. PushToString will deduce the type, call sizeof on it and use
// that size to call into the correct PushToStringImpl functor depending on
// whether it is 32 or 64 bit.

template <typename T, size_t size_of_t>
struct PushToStringImpl;

PushToStringImpl<T, 8>;

PushToStringImpl<T, 4>;

template <typename T>
void PushToString(T id, std::u32string* str) { … }

}  // namespace

// Implements the hashing of SENodes.
size_t SENodeHash::operator()(const SENode* node) const { … }

// This overload is the actual overload used by the node_cache_ set.
size_t SENodeHash::operator()(const std::unique_ptr<SENode>& node) const { … }

void SENode::DumpDot(std::ostream& out, bool recurse) const { … }

namespace {
class IsGreaterThanZero { … };
}  // namespace

bool ScalarEvolutionAnalysis::IsAlwaysGreaterThanZero(SENode* node,
                                                      bool* is_gt_zero) const { … }

bool ScalarEvolutionAnalysis::IsAlwaysGreaterOrEqualToZero(
    SENode* node, bool* is_ge_zero) const { … }

namespace {

// Remove |node| from the |mul| chain (of the form A * ... * |node| * ... * Z),
// if |node| is not in the chain, returns the original chain.
SENode* RemoveOneNodeFromMultiplyChain(SEMultiplyNode* mul,
                                       const SENode* node) { … }
}  // namespace

std::pair<SExpression, int64_t> SExpression::operator/(
    SExpression rhs_wrapper) const { … }

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