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

#include <limits>
#include <memory>
#include <utility>

#include "ir_builder.h"
#include "source/latest_version_glsl_std_450_header.h"
#include "source/opt/ir_context.h"

namespace spvtools {
namespace opt {
namespace {

constexpr uint32_t kExtractCompositeIdInIdx = …;
constexpr uint32_t kInsertObjectIdInIdx = …;
constexpr uint32_t kInsertCompositeIdInIdx = …;
constexpr uint32_t kExtInstSetIdInIdx = …;
constexpr uint32_t kExtInstInstructionInIdx = …;
constexpr uint32_t kFMixXIdInIdx = …;
constexpr uint32_t kFMixYIdInIdx = …;
constexpr uint32_t kFMixAIdInIdx = …;
constexpr uint32_t kStoreObjectInIdx = …;

// Some image instructions may contain an "image operands" argument.
// Returns the operand index for the "image operands".
// Returns -1 if the instruction does not have image operands.
int32_t ImageOperandsMaskInOperandIndex(Instruction* inst) { … }

// Returns the element width of |type|.
uint32_t ElementWidth(const analysis::Type* type) { … }

// Returns true if |type| is Float or a vector of Float.
bool HasFloatingPoint(const analysis::Type* type) { … }

// Returns false if |val| is NaN, infinite or subnormal.
template <typename T>
bool IsValidResult(T val) { … }

// Returns true if `type` is a cooperative matrix.
bool IsCooperativeMatrix(const analysis::Type* type) { … }

const analysis::Constant* ConstInput(
    const std::vector<const analysis::Constant*>& constants) { … }

Instruction* NonConstInput(IRContext* context, const analysis::Constant* c,
                           Instruction* inst) { … }

std::vector<uint32_t> ExtractInts(uint64_t val) { … }

std::vector<uint32_t> GetWordsFromScalarIntConstant(
    const analysis::IntConstant* c) { … }

std::vector<uint32_t> GetWordsFromScalarFloatConstant(
    const analysis::FloatConstant* c) { … }

std::vector<uint32_t> GetWordsFromNumericScalarOrVectorConstant(
    analysis::ConstantManager* const_mgr, const analysis::Constant* c) { … }

const analysis::Constant* ConvertWordsToNumericScalarOrVectorConstant(
    analysis::ConstantManager* const_mgr, const std::vector<uint32_t>& words,
    const analysis::Type* type) { … }

// Returns the negation of |c|. |c| must be a 32 or 64 bit floating point
// constant.
uint32_t NegateFloatingPointConstant(analysis::ConstantManager* const_mgr,
                                     const analysis::Constant* c) { … }

// Negates the integer constant |c|. Returns the id of the defining instruction.
uint32_t NegateIntegerConstant(analysis::ConstantManager* const_mgr,
                               const analysis::Constant* c) { … }

// Negates the vector constant |c|. Returns the id of the defining instruction.
uint32_t NegateVectorConstant(analysis::ConstantManager* const_mgr,
                              const analysis::Constant* c) { … }

// Negates |c|. Returns the id of the defining instruction.
uint32_t NegateConstant(analysis::ConstantManager* const_mgr,
                        const analysis::Constant* c) { … }

// Takes the reciprocal of |c|. |c|'s type must be Float or a vector of Float.
// Returns 0 if the reciprocal is NaN, infinite or subnormal.
uint32_t Reciprocal(analysis::ConstantManager* const_mgr,
                    const analysis::Constant* c) { … }

// Replaces fdiv where second operand is constant with fmul.
FoldingRule ReciprocalFDiv() { … }

// Elides consecutive negate instructions.
FoldingRule MergeNegateArithmetic() { … }

// Merges negate into a mul or div operation if that operation contains a
// constant operand.
// Cases:
// -(x * 2) = x * -2
// -(2 * x) = x * -2
// -(x / 2) = x / -2
// -(2 / x) = -2 / x
FoldingRule MergeNegateMulDivArithmetic() { … }

// Merges negate into a add or sub operation if that operation contains a
// constant operand.
// Cases:
// -(x + 2) = -2 - x
// -(2 + x) = -2 - x
// -(x - 2) = 2 - x
// -(2 - x) = x - 2
FoldingRule MergeNegateAddSubArithmetic() { … }

// Returns true if |c| has a zero element.
bool HasZero(const analysis::Constant* c) { … }

// Performs |input1| |opcode| |input2| and returns the merged constant result
// id. Returns 0 if the result is not a valid value. The input types must be
// Float.
uint32_t PerformFloatingPointOperation(analysis::ConstantManager* const_mgr,
                                       spv::Op opcode,
                                       const analysis::Constant* input1,
                                       const analysis::Constant* input2) { … }

// Performs |input1| |opcode| |input2| and returns the merged constant result
// id. Returns 0 if the result is not a valid value. The input types must be
// Integers.
uint32_t PerformIntegerOperation(analysis::ConstantManager* const_mgr,
                                 spv::Op opcode,
                                 const analysis::Constant* input1,
                                 const analysis::Constant* input2) { … }

// Performs |input1| |opcode| |input2| and returns the merged constant result
// id. Returns 0 if the result is not a valid value. The input types must be
// Integers, Floats or Vectors of such.
uint32_t PerformOperation(analysis::ConstantManager* const_mgr, spv::Op opcode,
                          const analysis::Constant* input1,
                          const analysis::Constant* input2) { … }

// Merges consecutive multiplies where each contains one constant operand.
// Cases:
// 2 * (x * 2) = x * 4
// 2 * (2 * x) = x * 4
// (x * 2) * 2 = x * 4
// (2 * x) * 2 = x * 4
FoldingRule MergeMulMulArithmetic() { … }

// Merges divides into subsequent multiplies if each instruction contains one
// constant operand. Does not support integer operations.
// Cases:
// 2 * (x / 2) = x * 1
// 2 * (2 / x) = 4 / x
// (x / 2) * 2 = x * 1
// (2 / x) * 2 = 4 / x
// (y / x) * x = y
// x * (y / x) = y
FoldingRule MergeMulDivArithmetic() { … }

// Merges multiply of constant and negation.
// Cases:
// (-x) * 2 = x * -2
// 2 * (-x) = x * -2
FoldingRule MergeMulNegateArithmetic() { … }

// Merges consecutive divides if each instruction contains one constant operand.
// Does not support integer division.
// Cases:
// 2 / (x / 2) = 4 / x
// 4 / (2 / x) = 2 * x
// (4 / x) / 2 = 2 / x
// (x / 2) / 2 = x / 4
FoldingRule MergeDivDivArithmetic() { … }

// Fold multiplies succeeded by divides where each instruction contains a
// constant operand. Does not support integer divide.
// Cases:
// 4 / (x * 2) = 2 / x
// 4 / (2 * x) = 2 / x
// (x * 4) / 2 = x * 2
// (4 * x) / 2 = x * 2
// (x * y) / x = y
// (y * x) / x = y
FoldingRule MergeDivMulArithmetic() { … }

// Fold divides of a constant and a negation.
// Cases:
// (-x) / 2 = x / -2
// 2 / (-x) = -2 / x
FoldingRule MergeDivNegateArithmetic() { … }

// Folds addition of a constant and a negation.
// Cases:
// (-x) + 2 = 2 - x
// 2 + (-x) = 2 - x
FoldingRule MergeAddNegateArithmetic() { … }

// Folds subtraction of a constant and a negation.
// Cases:
// (-x) - 2 = -2 - x
// 2 - (-x) = x + 2
FoldingRule MergeSubNegateArithmetic() { … }

// Folds addition of an addition where each operation has a constant operand.
// Cases:
// (x + 2) + 2 = x + 4
// (2 + x) + 2 = x + 4
// 2 + (x + 2) = x + 4
// 2 + (2 + x) = x + 4
FoldingRule MergeAddAddArithmetic() { … }

// Folds addition of a subtraction where each operation has a constant operand.
// Cases:
// (x - 2) + 2 = x + 0
// (2 - x) + 2 = 4 - x
// 2 + (x - 2) = x + 0
// 2 + (2 - x) = 4 - x
FoldingRule MergeAddSubArithmetic() { … }

// Folds subtraction of an addition where each operand has a constant operand.
// Cases:
// (x + 2) - 2 = x + 0
// (2 + x) - 2 = x + 0
// 2 - (x + 2) = 0 - x
// 2 - (2 + x) = 0 - x
FoldingRule MergeSubAddArithmetic() { … }

// Folds subtraction of a subtraction where each operand has a constant operand.
// Cases:
// (x - 2) - 2 = x - 4
// (2 - x) - 2 = 0 - x
// 2 - (x - 2) = 4 - x
// 2 - (2 - x) = x + 0
FoldingRule MergeSubSubArithmetic() { … }

// Helper function for MergeGenericAddSubArithmetic. If |addend| and
// subtrahend of |sub| is the same, merge to copy of minuend of |sub|.
bool MergeGenericAddendSub(uint32_t addend, uint32_t sub, Instruction* inst) { … }

// Folds addition of a subtraction where the subtrahend is equal to the
// other addend. Return a copy of the minuend. Accepts generic (const and
// non-const) operands.
// Cases:
// (a - b) + b = a
// b + (a - b) = a
FoldingRule MergeGenericAddSubArithmetic() { … }

// Helper function for FactorAddMuls. If |factor0_0| is the same as |factor1_0|,
// generate |factor0_0| * (|factor0_1| + |factor1_1|).
bool FactorAddMulsOpnds(uint32_t factor0_0, uint32_t factor0_1,
                        uint32_t factor1_0, uint32_t factor1_1,
                        Instruction* inst) { … }

// Perform the following factoring identity, handling all operand order
// combinations: (a * b) + (a * c) = a * (b + c)
FoldingRule FactorAddMuls() { … }

FoldingRule IntMultipleBy1() { … }

// Returns the number of elements that the |index|th in operand in |inst|
// contributes to the result of |inst|.  |inst| must be an
// OpCompositeConstructInstruction.
uint32_t GetNumOfElementsContributedByOperand(IRContext* context,
                                              const Instruction* inst,
                                              uint32_t index) { … }

// Returns the in-operands for an OpCompositeExtract instruction that are needed
// to extract the |result_index|th element in the result of |inst| without using
// the result of |inst|. Returns the empty vector if |result_index| is
// out-of-bounds. |inst| must be an |OpCompositeConstruct| instruction.
std::vector<Operand> GetExtractOperandsForElementOfCompositeConstruct(
    IRContext* context, const Instruction* inst, uint32_t result_index) { … }

bool CompositeConstructFeedingExtract(
    IRContext* context, Instruction* inst,
    const std::vector<const analysis::Constant*>&) { … }

// Walks the indexes chain from |start| to |end| of an OpCompositeInsert or
// OpCompositeExtract instruction, and returns the type id of the final element
// being accessed. Returns 0 if a valid type could not be found.
uint32_t GetElementType(uint32_t type_id, Instruction::iterator start,
                        Instruction::iterator end,
                        const analysis::DefUseManager* def_use_manager) { … }

// Returns true of |inst_1| and |inst_2| have the same indexes that will be used
// to index into a composite object, excluding the last index.  The two
// instructions must have the same opcode, and be either OpCompositeExtract or
// OpCompositeInsert instructions.
bool HaveSameIndexesExceptForLast(Instruction* inst_1, Instruction* inst_2) { … }

// If the OpCompositeConstruct is simply putting back together elements that
// where extracted from the same source, we can simply reuse the source.
//
// This is a common code pattern because of the way that scalar replacement
// works.
bool CompositeExtractFeedingConstruct(
    IRContext* context, Instruction* inst,
    const std::vector<const analysis::Constant*>&) { … }

FoldingRule InsertFeedingExtract() { … }

// When a VectorShuffle is feeding an Extract, we can extract from one of the
// operands of the VectorShuffle.  We just need to adjust the index in the
// extract instruction.
FoldingRule VectorShuffleFeedingExtract() { … }

// When an FMix with is feeding an Extract that extracts an element whose
// corresponding |a| in the FMix is 0 or 1, we can extract from one of the
// operands of the FMix.
FoldingRule FMixFeedingExtract() { … }

// Returns the number of elements in the composite type |type|.  Returns 0 if
// |type| is a scalar value. Return UINT32_MAX when the size is unknown at
// compile time.
uint32_t GetNumberOfElements(const analysis::Type* type) { … }

// Returns a map with the set of values that were inserted into an object by
// the chain of OpCompositeInsertInstruction starting with |inst|.
// The map will map the index to the value inserted at that index. An empty map
// will be returned if the map could not be properly generated.
std::map<uint32_t, uint32_t> GetInsertedValues(Instruction* inst) { … }

// Returns true of there is an entry in |values_inserted| for every element of
// |Type|.
bool DoInsertedValuesCoverEntireObject(
    const analysis::Type* type, std::map<uint32_t, uint32_t>& values_inserted) { … }

// Returns id of the type of the element that immediately contains the element
// being inserted by the OpCompositeInsert instruction |inst|. Returns 0 if it
// could not be found.
uint32_t GetContainerTypeId(Instruction* inst) { … }

// Returns an OpCompositeConstruct instruction that build an object with
// |type_id| out of the values in |values_inserted|.  Each value will be
// placed at the index corresponding to the value.  The new instruction will
// be placed before |insert_before|.
Instruction* BuildCompositeConstruct(
    uint32_t type_id, const std::map<uint32_t, uint32_t>& values_inserted,
    Instruction* insert_before) { … }

// Replaces the OpCompositeInsert |inst| that inserts |construct| into the same
// object as |inst| with final index removed.  If the resulting
// OpCompositeInsert instruction would have no remaining indexes, the
// instruction is replaced with an OpCopyObject instead.
void InsertConstructedObject(Instruction* inst, const Instruction* construct) { … }

// Replaces a series of |OpCompositeInsert| instruction that cover the entire
// object with an |OpCompositeConstruct|.
bool CompositeInsertToCompositeConstruct(
    IRContext* context, Instruction* inst,
    const std::vector<const analysis::Constant*>&) { … }

FoldingRule RedundantPhi() { … }

FoldingRule BitCastScalarOrVector() { … }

FoldingRule RedundantSelect() { … }

enum class FloatConstantKind { … };

FloatConstantKind getFloatConstantKind(const analysis::Constant* constant) { … }

FoldingRule RedundantFAdd() { … }

FoldingRule RedundantFSub() { … }

FoldingRule RedundantFMul() { … }

FoldingRule RedundantFDiv() { … }

FoldingRule RedundantFMix() { … }

// This rule handles addition of zero for integers.
FoldingRule RedundantIAdd() { … }

// This rule look for a dot with a constant vector containing a single 1 and
// the rest 0s.  This is the same as doing an extract.
FoldingRule DotProductDoingExtract() { … }

// If we are storing an undef, then we can remove the store.
//
// TODO: We can do something similar for OpImageWrite, but checking for volatile
// is complicated.  Waiting to see if it is needed.
FoldingRule StoringUndef() { … }

FoldingRule VectorShuffleFeedingShuffle() { … }

// Removes duplicate ids from the interface list of an OpEntryPoint
// instruction.
FoldingRule RemoveRedundantOperands() { … }

// If an image instruction's operand is a constant, updates the image operand
// flag from Offset to ConstOffset.
FoldingRule UpdateImageOperands() { … }

}  // namespace

void FoldingRules::AddFoldingRules() { … }
}  // namespace opt
}  // namespace spvtools
chromium/third_party/spirv-tools/src/source/opt/folding_rules.cpp
