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
26namespace spvtools {
27namespace opt {
28
29class 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_
188