scalar_analysis_simplification.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 <functional>
#include <map>
#include <memory>
#include <set>
#include <utility>
#include <vector>

#include "source/opt/scalar_analysis.h"

// Simplifies scalar analysis DAGs.
//
// 1. Given a node passed to SimplifyExpression we first simplify the graph by
// calling SimplifyPolynomial. This groups like nodes following basic arithmetic
// rules, so multiple adds of the same load instruction could be grouped into a
// single multiply of that instruction. SimplifyPolynomial will traverse the DAG
// and build up an accumulator buffer for each class of instruction it finds.
// For example take the loop:
// for (i=0, i<N; i++) { i+B+23+4+B+C; }
// In this example the expression "i+B+23+4+B+C" has four classes of
// instruction, induction variable i, the two value unknowns B and C, and the
// constants. The accumulator buffer is then used to rebuild the graph using
// the accumulation of each type. This example would then be folded into
// i+2*B+C+27.
//
// This new graph contains a single add node (or if only one type found then
// just that node) with each of the like terms (or multiplication node) as a
// child.
//
// 2. FoldRecurrentAddExpressions is then called on this new DAG. This will take
// RecurrentAddExpressions which are with respect to the same loop and fold them
// into a single new RecurrentAddExpression with respect to that same loop. An
// expression can have multiple RecurrentAddExpression's with respect to
// different loops in the case of nested loops. These expressions cannot be
// folded further. For example:
//
// for (i=0; i<N;i++) for(j=0,k=1; j<N;++j,++k)
//
// The 'j' and 'k' are RecurrentAddExpression with respect to the second loop
// and 'i' to the first. If 'j' and 'k' are used in an expression together then
// they will be folded into a new RecurrentAddExpression with respect to the
// second loop in that expression.
//
//
// 3. If the DAG now only contains a single RecurrentAddExpression we can now
// perform a final optimization SimplifyRecurrentAddExpression. This will
// transform the entire DAG into a RecurrentAddExpression. Additions to the
// RecurrentAddExpression are added to the offset field and multiplications to
// the coefficient.
//

namespace spvtools {
namespace opt {

// Implementation of the functions which are used to simplify the graph. Graphs
// of unknowns, multiplies, additions, and constants can be turned into a linear
// add node with each term as a child. For instance a large graph built from, X
// + X*2 + Y - Y*3 + 4 - 1, would become a single add expression with the
// children X*3, -Y*2, and the constant 3. Graphs containing a recurrent
// expression will be simplified to represent the entire graph around a single
// recurrent expression. So for an induction variable (i=0, i++) if you add 1 to
// i in an expression we can rewrite the graph of that expression to be a single
// recurrent expression of (i=1,i++).
class SENodeSimplifyImpl { … };

// From a |multiply| build up the accumulator objects.
bool SENodeSimplifyImpl::AccumulatorsFromMultiply(SENode* multiply,
                                                  bool negation) { … }

SENode* SENodeSimplifyImpl::Simplify() { … }

// Traverse the graph to build up the accumulator objects.
void SENodeSimplifyImpl::GatherAccumulatorsFromChildNodes(SENode* new_node,
                                                          SENode* child,
                                                          bool negation) { … }

SERecurrentNode* SENodeSimplifyImpl::UpdateCoefficient(
    SERecurrentNode* recurrent, int64_t coefficient_update) const { … }

// Simplify all the terms in the polynomial function.
SENode* SENodeSimplifyImpl::SimplifyPolynomial() { … }

SENode* SENodeSimplifyImpl::FoldRecurrentAddExpressions(SENode* root) { … }

SENode* SENodeSimplifyImpl::EliminateZeroCoefficientRecurrents(SENode* node) { … }

SENode* SENodeSimplifyImpl::SimplifyRecurrentAddExpression(
    SERecurrentNode* recurrent_expr) { … }

/*
 * Scalar Analysis simplification public methods.
 */

SENode* ScalarEvolutionAnalysis::SimplifyExpression(SENode* node) { … }

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