| 1 |
// Copyright (c) 2017 Google Inc. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
#ifndef SOURCE_OPT_FOLD_H_ |
| 16 |
#define SOURCE_OPT_FOLD_H_ |
| 17 |
|
| 18 |
#include <cstdint> |
| 19 |
#include <vector> |
| 20 |
|
| 21 |
#include "source/opt/const_folding_rules.h" |
| 22 |
#include "source/opt/constants.h" |
| 23 |
#include "source/opt/def_use_manager.h" |
| 24 |
#include "source/opt/folding_rules.h" |
| 25 |
|
| 26 |
namespace spvtools { |
| 27 |
namespace opt { |
| 28 |
|
| 29 |
class InstructionFolder { |
| 30 |
public: |
| 31 |
explicit InstructionFolder(IRContext* context) |
| 32 |
: context_(context), |
| 33 |
const_folding_rules_(new ConstantFoldingRules(context)), |
| 34 |
folding_rules_(new FoldingRules(context)) { |
| 35 |
folding_rules_->AddFoldingRules(); |
| 36 |
const_folding_rules_->AddFoldingRules(); |
| 37 |
} |
| 38 |
|
| 39 |
explicit InstructionFolder( |
| 40 |
IRContext* context, std::unique_ptr<FoldingRules>&& folding_rules, |
| 41 |
std::unique_ptr<ConstantFoldingRules>&& constant_folding_rules) |
| 42 |
: context_(context), |
| 43 |
const_folding_rules_(std::move(constant_folding_rules)), |
| 44 |
folding_rules_(std::move(folding_rules)) { |
| 45 |
folding_rules_->AddFoldingRules(); |
| 46 |
const_folding_rules_->AddFoldingRules(); |
| 47 |
} |
| 48 |
|
| 49 |
// Returns the result of folding a scalar instruction with the given |opcode| |
| 50 |
// and |operands|. Each entry in |operands| is a pointer to an |
| 51 |
// analysis::Constant instance, which should've been created with the constant |
| 52 |
// manager (See IRContext::get_constant_mgr). |
| 53 |
// |
| 54 |
// It is an error to call this function with an opcode that does not pass the |
| 55 |
// IsFoldableOpcode test. If any error occurs during folding, the folder will |
| 56 |
// fail with a call to assert. |
| 57 |
uint32_t FoldScalars( |
| 58 |
SpvOp opcode, |
| 59 |
const std::vector<const analysis::Constant*>& operands) const; |
| 60 |
|
| 61 |
// Returns the result of performing an operation with the given |opcode| over |
| 62 |
// constant vectors with |num_dims| dimensions. Each entry in |operands| is a |
| 63 |
// pointer to an analysis::Constant instance, which should've been created |
| 64 |
// with the constant manager (See IRContext::get_constant_mgr). |
| 65 |
// |
| 66 |
// This function iterates through the given vector type constant operands and |
| 67 |
// calculates the result for each element of the result vector to return. |
| 68 |
// Vectors with longer than 32-bit scalar components are not accepted in this |
| 69 |
// function. |
| 70 |
// |
| 71 |
// It is an error to call this function with an opcode that does not pass the |
| 72 |
// IsFoldableOpcode test. If any error occurs during folding, the folder will |
| 73 |
// fail with a call to assert. |
| 74 |
std::vector<uint32_t> FoldVectors( |
| 75 |
SpvOp opcode, uint32_t num_dims, |
| 76 |
const std::vector<const analysis::Constant*>& operands) const; |
| 77 |
|
| 78 |
// Returns true if |opcode| represents an operation handled by FoldScalars or |
| 79 |
// FoldVectors. |
| 80 |
bool IsFoldableOpcode(SpvOp opcode) const; |
| 81 |
|
| 82 |
// Returns true if |cst| is supported by FoldScalars and FoldVectors. |
| 83 |
bool IsFoldableConstant(const analysis::Constant* cst) const; |
| 84 |
|
| 85 |
// Returns true if |FoldInstructionToConstant| could fold an instruction whose |
| 86 |
// result type is |type_inst|. |
| 87 |
bool IsFoldableType(Instruction* type_inst) const; |
| 88 |
|
| 89 |
// Tries to fold |inst| to a single constant, when the input ids to |inst| |
| 90 |
// have been substituted using |id_map|. Returns a pointer to the OpConstant* |
| 91 |
// instruction if successful. If necessary, a new constant instruction is |
| 92 |
// created and placed in the global values section. |
| 93 |
// |
| 94 |
// |id_map| is a function that takes one result id and returns another. It |
| 95 |
// can be used for things like CCP where it is known that some ids contain a |
| 96 |
// constant, but the instruction itself has not been updated yet. This can |
| 97 |
// map those ids to the appropriate constants. |
| 98 |
Instruction* FoldInstructionToConstant( |
| 99 |
Instruction* inst, std::function<uint32_t(uint32_t)> id_map) const; |
| 100 |
// Returns true if |inst| can be folded into a simpler instruction. |
| 101 |
// If |inst| can be simplified, |inst| is overwritten with the simplified |
| 102 |
// instruction reusing the same result id. |
| 103 |
// |
| 104 |
// If |inst| is simplified, it is possible that the resulting code in invalid |
| 105 |
// because the instruction is in a bad location. Callers of this function |
| 106 |
// have to handle the following cases: |
| 107 |
// |
| 108 |
// 1) An OpPhi becomes and OpCopyObject - If there are OpPhi instruction after |
| 109 |
// |inst| in a basic block then this is invalid. The caller must fix this |
| 110 |
// up. |
| 111 |
bool FoldInstruction(Instruction* inst) const; |
| 112 |
|
| 113 |
// Return true if this opcode has a const folding rule associtated with it. |
| 114 |
bool HasConstFoldingRule(const Instruction* inst) const { |
| 115 |
return GetConstantFoldingRules().HasFoldingRule(inst); |
| 116 |
} |
| 117 |
|
| 118 |
private: |
| 119 |
// Returns a reference to the ConstnatFoldingRules instance. |
| 120 |
const ConstantFoldingRules& GetConstantFoldingRules() const { |
| 121 |
return *const_folding_rules_; |
| 122 |
} |
| 123 |
|
| 124 |
// Returns a reference to the FoldingRules instance. |
| 125 |
const FoldingRules& GetFoldingRules() const { return *folding_rules_; } |
| 126 |
|
| 127 |
// Returns the single-word result from performing the given unary operation on |
| 128 |
// the operand value which is passed in as a 32-bit word. |
| 129 |
uint32_t UnaryOperate(SpvOp opcode, uint32_t operand) const; |
| 130 |
|
| 131 |
// Returns the single-word result from performing the given binary operation |
| 132 |
// on the operand values which are passed in as two 32-bit word. |
| 133 |
uint32_t BinaryOperate(SpvOp opcode, uint32_t a, uint32_t b) const; |
| 134 |
|
| 135 |
// Returns the single-word result from performing the given ternary operation |
| 136 |
// on the operand values which are passed in as three 32-bit word. |
| 137 |
uint32_t TernaryOperate(SpvOp opcode, uint32_t a, uint32_t b, |
| 138 |
uint32_t c) const; |
| 139 |
|
| 140 |
// Returns the single-word result from performing the given operation on the |
| 141 |
// operand words. This only works with 32-bit operations and uses boolean |
| 142 |
// convention that 0u is false, and anything else is boolean true. |
| 143 |
// TODO(qining): Support operands other than 32-bit wide. |
| 144 |
uint32_t OperateWords(SpvOp opcode, |
| 145 |
const std::vector<uint32_t>& operand_words) const; |
| 146 |
|
| 147 |
bool FoldInstructionInternal(Instruction* inst) const; |
| 148 |
|
| 149 |
// Returns true if |inst| is a binary operation that takes two integers as |
| 150 |
// parameters and folds to a constant that can be represented as an unsigned |
| 151 |
// 32-bit value when the ids have been replaced by |id_map|. If |inst| can be |
| 152 |
// folded, the resulting value is returned in |*result|. Valid result types |
| 153 |
// for the instruction are any integer (signed or unsigned) with 32-bits or |
| 154 |
// less, or a boolean value. |
| 155 |
bool FoldBinaryIntegerOpToConstant( |
| 156 |
Instruction* inst, const std::function<uint32_t(uint32_t)>& id_map, |
| 157 |
uint32_t* result) const; |
| 158 |
|
| 159 |
// Returns true if |inst| is a binary operation on two boolean values, and |
| 160 |
// folds |
| 161 |
// to a constant boolean value when the ids have been replaced using |id_map|. |
| 162 |
// If |inst| can be folded, the result value is returned in |*result|. |
| 163 |
bool FoldBinaryBooleanOpToConstant( |
| 164 |
Instruction* inst, const std::function<uint32_t(uint32_t)>& id_map, |
| 165 |
uint32_t* result) const; |
| 166 |
|
| 167 |
// Returns true if |inst| can be folded to an constant when the ids have been |
| 168 |
// substituted using id_map. If it can, the value is returned in |result|. If |
| 169 |
// not, |result| is unchanged. It is assumed that not all operands are |
| 170 |
// constant. Those cases are handled by |FoldScalar|. |
| 171 |
bool FoldIntegerOpToConstant(Instruction* inst, |
| 172 |
const std::function<uint32_t(uint32_t)>& id_map, |
| 173 |
uint32_t* result) const; |
| 174 |
|
| 175 |
IRContext* context_; |
| 176 |
|
| 177 |
// Folding rules used by |FoldInstructionToConstant| and |FoldInstruction|. |
| 178 |
std::unique_ptr<ConstantFoldingRules> const_folding_rules_; |
| 179 |
|
| 180 |
// Folding rules used by |FoldInstruction|. |
| 181 |
std::unique_ptr<FoldingRules> folding_rules_; |
| 182 |
}; |
| 183 |
|
| 184 |
} // namespace opt |
| 185 |
} // namespace spvtools |
| 186 |
|
| 187 |
#endif // SOURCE_OPT_FOLD_H_ |