loop_dependence.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/loop_dependence.h"

#include <functional>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

#include "source/opt/instruction.h"
#include "source/opt/scalar_analysis_nodes.h"

namespace spvtools {
namespace opt {

SubscriptPair;

namespace {

// Calculate the greatest common divisor of a & b using Stein's algorithm.
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm
int64_t GreatestCommonDivisor(int64_t a, int64_t b) { … }

// Check if node is affine, ie in the form: a0*i0 + a1*i1 + ... an*in + c
// and contains only the following types of nodes: SERecurrentNode, SEAddNode
// and SEConstantNode
bool IsInCorrectFormForGCDTest(SENode* node) { … }

// If |node| is an SERecurrentNode then returns |node| or if |node| is an
// SEAddNode returns a vector of SERecurrentNode that are its children.
std::vector<SERecurrentNode*> GetAllTopLevelRecurrences(SENode* node) { … }

// If |node| is an SEConstantNode then returns |node| or if |node| is an
// SEAddNode returns a vector of SEConstantNode that are its children.
std::vector<SEConstantNode*> GetAllTopLevelConstants(SENode* node) { … }

bool AreOffsetsAndCoefficientsConstant(
    const std::vector<SERecurrentNode*>& nodes) { … }

// Fold all SEConstantNode that appear in |recurrences| and |constants| into a
// single integer value.
int64_t CalculateConstantTerm(const std::vector<SERecurrentNode*>& recurrences,
                              const std::vector<SEConstantNode*>& constants) { … }

int64_t CalculateGCDFromCoefficients(
    const std::vector<SERecurrentNode*>& recurrences, int64_t running_gcd) { … }

// Compare 2 fractions while first normalizing them, e.g. 2/4 and 4/8 will both
// be simplified to 1/2 and then determined to be equal.
bool NormalizeAndCompareFractions(int64_t numerator_0, int64_t denominator_0,
                                  int64_t numerator_1, int64_t denominator_1) { … }

}  // namespace

bool LoopDependenceAnalysis::GetDependence(const Instruction* source,
                                           const Instruction* destination,
                                           DistanceVector* distance_vector) { … }

bool LoopDependenceAnalysis::ZIVTest(
    const std::pair<SENode*, SENode*>& subscript_pair) { … }

bool LoopDependenceAnalysis::SIVTest(
    const std::pair<SENode*, SENode*>& subscript_pair,
    DistanceVector* distance_vector) { … }

bool LoopDependenceAnalysis::StrongSIVTest(SENode* source, SENode* destination,
                                           SENode* coefficient,
                                           DistanceEntry* distance_entry) { … }

bool LoopDependenceAnalysis::SymbolicStrongSIVTest(
    SENode* source, SENode* destination, SENode* coefficient,
    DistanceEntry* distance_entry) { … }

bool LoopDependenceAnalysis::WeakZeroSourceSIVTest(
    SENode* source, SERecurrentNode* destination, SENode* coefficient,
    DistanceEntry* distance_entry) { … }

bool LoopDependenceAnalysis::WeakZeroDestinationSIVTest(
    SERecurrentNode* source, SENode* destination, SENode* coefficient,
    DistanceEntry* distance_entry) { … }

bool LoopDependenceAnalysis::WeakCrossingSIVTest(
    SENode* source, SENode* destination, SENode* coefficient,
    DistanceEntry* distance_entry) { … }

// Perform the GCD test if both, the source and the destination nodes, are in
// the form a0*i0 + a1*i1 + ... an*in + c.
bool LoopDependenceAnalysis::GCDMIVTest(
    const std::pair<SENode*, SENode*>& subscript_pair) { … }

PartitionedSubscripts;
PartitionedSubscripts LoopDependenceAnalysis::PartitionSubscripts(
    const std::vector<Instruction*>& source_subscripts,
    const std::vector<Instruction*>& destination_subscripts) { … }

Constraint* LoopDependenceAnalysis::IntersectConstraints(
    Constraint* constraint_0, Constraint* constraint_1,
    const SENode* lower_bound, const SENode* upper_bound) { … }

// Propagate constraints function as described in section 5 of Practical
// Dependence Testing, Goff, Kennedy, Tseng, 1991.
SubscriptPair LoopDependenceAnalysis::PropagateConstraints(
    const SubscriptPair& subscript_pair,
    const std::vector<Constraint*>& constraints) { … }

bool LoopDependenceAnalysis::DeltaTest(
    const std::vector<SubscriptPair>& coupled_subscripts,
    DistanceVector* dv_entry) { … }

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