1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "instruction_simplifier_arm64.h"
18
19 #include "common_arm64.h"
20 #include "instruction_simplifier.h"
21 #include "instruction_simplifier_shared.h"
22 #include "mirror/array-inl.h"
23 #include "mirror/string.h"
24
25 namespace art HIDDEN {
26
27 using helpers::CanFitInShifterOperand;
28 using helpers::HasShifterOperand;
29 using helpers::IsSubRightSubLeftShl;
30
31 namespace arm64 {
32
33 using helpers::ShifterOperandSupportsExtension;
34
35 class InstructionSimplifierArm64Visitor final : public HGraphVisitor {
36 public:
InstructionSimplifierArm64Visitor(HGraph * graph,CodeGenerator * codegen,OptimizingCompilerStats * stats)37 InstructionSimplifierArm64Visitor(
38 HGraph* graph, CodeGenerator* codegen, OptimizingCompilerStats* stats)
39 : HGraphVisitor(graph), codegen_(codegen), stats_(stats) {}
40
41 private:
RecordSimplification()42 void RecordSimplification() {
43 MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSimplificationsArch);
44 }
45
46 bool TryMergeIntoUsersShifterOperand(HInstruction* instruction);
47 bool TryMergeIntoShifterOperand(HInstruction* use,
48 HInstruction* bitfield_op,
49 bool do_merge);
CanMergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op)50 bool CanMergeIntoShifterOperand(HInstruction* use, HInstruction* bitfield_op) {
51 return TryMergeIntoShifterOperand(use, bitfield_op, /* do_merge= */ false);
52 }
MergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op)53 bool MergeIntoShifterOperand(HInstruction* use, HInstruction* bitfield_op) {
54 DCHECK(CanMergeIntoShifterOperand(use, bitfield_op));
55 return TryMergeIntoShifterOperand(use, bitfield_op, /* do_merge= */ true);
56 }
57
58 /**
59 * This simplifier uses a special-purpose BB visitor.
60 * (1) No need to visit Phi nodes.
61 * (2) Since statements can be removed in a "forward" fashion,
62 * the visitor should test if each statement is still there.
63 */
VisitBasicBlock(HBasicBlock * block)64 void VisitBasicBlock(HBasicBlock* block) override {
65 // TODO: fragile iteration, provide more robust iterators?
66 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
67 HInstruction* instruction = it.Current();
68 if (instruction->IsInBlock()) {
69 instruction->Accept(this);
70 }
71 }
72 }
73
74 // HInstruction visitors, sorted alphabetically.
75 void VisitAnd(HAnd* instruction) override;
76 void VisitArrayGet(HArrayGet* instruction) override;
77 void VisitArraySet(HArraySet* instruction) override;
78 void VisitMul(HMul* instruction) override;
79 void VisitOr(HOr* instruction) override;
80 void VisitRol(HRol* instruction) override;
81 void VisitShl(HShl* instruction) override;
82 void VisitShr(HShr* instruction) override;
83 void VisitSub(HSub* instruction) override;
84 void VisitTypeConversion(HTypeConversion* instruction) override;
85 void VisitUShr(HUShr* instruction) override;
86 void VisitXor(HXor* instruction) override;
87 void VisitVecLoad(HVecLoad* instruction) override;
88 void VisitVecStore(HVecStore* instruction) override;
89
90 CodeGenerator* codegen_;
91 OptimizingCompilerStats* stats_;
92 };
93
TryMergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op,bool do_merge)94 bool InstructionSimplifierArm64Visitor::TryMergeIntoShifterOperand(HInstruction* use,
95 HInstruction* bitfield_op,
96 bool do_merge) {
97 DCHECK(HasShifterOperand(use, InstructionSet::kArm64));
98 DCHECK(use->IsBinaryOperation() || use->IsNeg());
99 DCHECK(CanFitInShifterOperand(bitfield_op));
100 DCHECK(!bitfield_op->HasEnvironmentUses());
101
102 DataType::Type type = use->GetType();
103 if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
104 return false;
105 }
106
107 HInstruction* left;
108 HInstruction* right;
109 if (use->IsBinaryOperation()) {
110 left = use->InputAt(0);
111 right = use->InputAt(1);
112 } else {
113 DCHECK(use->IsNeg());
114 right = use->AsNeg()->InputAt(0);
115 left = GetGraph()->GetConstant(right->GetType(), 0);
116 }
117 DCHECK(left == bitfield_op || right == bitfield_op);
118
119 if (left == right) {
120 // TODO: Handle special transformations in this situation?
121 // For example should we transform `(x << 1) + (x << 1)` into `(x << 2)`?
122 // Or should this be part of a separate transformation logic?
123 return false;
124 }
125
126 bool is_commutative = use->IsBinaryOperation() && use->AsBinaryOperation()->IsCommutative();
127 HInstruction* other_input;
128 if (bitfield_op == right) {
129 other_input = left;
130 } else {
131 if (is_commutative) {
132 other_input = right;
133 } else {
134 return false;
135 }
136 }
137
138 HDataProcWithShifterOp::OpKind op_kind;
139 int shift_amount = 0;
140 HDataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
141
142 if (HDataProcWithShifterOp::IsExtensionOp(op_kind) && !ShifterOperandSupportsExtension(use)) {
143 return false;
144 }
145
146 if (do_merge) {
147 HDataProcWithShifterOp* alu_with_op =
148 new (GetGraph()->GetAllocator()) HDataProcWithShifterOp(use,
149 other_input,
150 bitfield_op->InputAt(0),
151 op_kind,
152 shift_amount,
153 use->GetDexPc());
154 use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
155 if (bitfield_op->GetUses().empty()) {
156 bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
157 }
158 RecordSimplification();
159 }
160
161 return true;
162 }
163
164 // Merge a bitfield move instruction into its uses if it can be merged in all of them.
TryMergeIntoUsersShifterOperand(HInstruction * bitfield_op)165 bool InstructionSimplifierArm64Visitor::TryMergeIntoUsersShifterOperand(HInstruction* bitfield_op) {
166 DCHECK(CanFitInShifterOperand(bitfield_op));
167
168 if (bitfield_op->HasEnvironmentUses()) {
169 return false;
170 }
171
172 const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
173
174 // Check whether we can merge the instruction in all its users' shifter operand.
175 for (const HUseListNode<HInstruction*>& use : uses) {
176 HInstruction* user = use.GetUser();
177 if (!HasShifterOperand(user, InstructionSet::kArm64)) {
178 return false;
179 }
180 if (!CanMergeIntoShifterOperand(user, bitfield_op)) {
181 return false;
182 }
183 }
184
185 // Merge the instruction into its uses.
186 for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
187 HInstruction* user = it->GetUser();
188 // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand().
189 ++it;
190 bool merged = MergeIntoShifterOperand(user, bitfield_op);
191 DCHECK(merged);
192 }
193
194 return true;
195 }
196
VisitAnd(HAnd * instruction)197 void InstructionSimplifierArm64Visitor::VisitAnd(HAnd* instruction) {
198 if (TryMergeNegatedInput(instruction)) {
199 RecordSimplification();
200 }
201 }
202
VisitArrayGet(HArrayGet * instruction)203 void InstructionSimplifierArm64Visitor::VisitArrayGet(HArrayGet* instruction) {
204 size_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
205 if (TryExtractArrayAccessAddress(codegen_,
206 instruction,
207 instruction->GetArray(),
208 instruction->GetIndex(),
209 data_offset)) {
210 RecordSimplification();
211 }
212 }
213
VisitArraySet(HArraySet * instruction)214 void InstructionSimplifierArm64Visitor::VisitArraySet(HArraySet* instruction) {
215 size_t access_size = DataType::Size(instruction->GetComponentType());
216 size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value();
217 if (TryExtractArrayAccessAddress(codegen_,
218 instruction,
219 instruction->GetArray(),
220 instruction->GetIndex(),
221 data_offset)) {
222 RecordSimplification();
223 }
224 }
225
VisitMul(HMul * instruction)226 void InstructionSimplifierArm64Visitor::VisitMul(HMul* instruction) {
227 if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm64)) {
228 RecordSimplification();
229 }
230 }
231
VisitOr(HOr * instruction)232 void InstructionSimplifierArm64Visitor::VisitOr(HOr* instruction) {
233 if (TryMergeNegatedInput(instruction)) {
234 RecordSimplification();
235 }
236 }
237
VisitRol(HRol * rol)238 void InstructionSimplifierArm64Visitor::VisitRol(HRol* rol) {
239 UnfoldRotateLeft(rol);
240 RecordSimplification();
241 }
242
VisitShl(HShl * instruction)243 void InstructionSimplifierArm64Visitor::VisitShl(HShl* instruction) {
244 if (instruction->InputAt(1)->IsConstant()) {
245 TryMergeIntoUsersShifterOperand(instruction);
246 }
247 }
248
VisitShr(HShr * instruction)249 void InstructionSimplifierArm64Visitor::VisitShr(HShr* instruction) {
250 if (instruction->InputAt(1)->IsConstant()) {
251 TryMergeIntoUsersShifterOperand(instruction);
252 }
253 }
254
VisitSub(HSub * instruction)255 void InstructionSimplifierArm64Visitor::VisitSub(HSub* instruction) {
256 if (IsSubRightSubLeftShl(instruction)) {
257 HInstruction* shl = instruction->GetRight()->InputAt(0);
258 if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
259 if (TryMergeIntoUsersShifterOperand(shl)) {
260 return;
261 }
262 }
263 }
264
265 if (TryMergeWithAnd(instruction)) {
266 return;
267 }
268 }
269
VisitTypeConversion(HTypeConversion * instruction)270 void InstructionSimplifierArm64Visitor::VisitTypeConversion(HTypeConversion* instruction) {
271 DataType::Type result_type = instruction->GetResultType();
272 DataType::Type input_type = instruction->GetInputType();
273
274 if (input_type == result_type) {
275 // We let the arch-independent code handle this.
276 return;
277 }
278
279 if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) {
280 TryMergeIntoUsersShifterOperand(instruction);
281 }
282 }
283
VisitUShr(HUShr * instruction)284 void InstructionSimplifierArm64Visitor::VisitUShr(HUShr* instruction) {
285 if (instruction->InputAt(1)->IsConstant()) {
286 TryMergeIntoUsersShifterOperand(instruction);
287 }
288 }
289
VisitXor(HXor * instruction)290 void InstructionSimplifierArm64Visitor::VisitXor(HXor* instruction) {
291 if (TryMergeNegatedInput(instruction)) {
292 RecordSimplification();
293 }
294 }
295
VisitVecLoad(HVecLoad * instruction)296 void InstructionSimplifierArm64Visitor::VisitVecLoad(HVecLoad* instruction) {
297 if (!instruction->IsPredicated() && !instruction->IsStringCharAt() &&
298 TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
299 RecordSimplification();
300 } else if (instruction->IsPredicated()) {
301 size_t size = DataType::Size(instruction->GetPackedType());
302 size_t offset = mirror::Array::DataOffset(size).Uint32Value();
303 if (TryExtractArrayAccessAddress(
304 codegen_, instruction, instruction->GetArray(), instruction->GetIndex(), offset)) {
305 RecordSimplification();
306 }
307 }
308 }
309
VisitVecStore(HVecStore * instruction)310 void InstructionSimplifierArm64Visitor::VisitVecStore(HVecStore* instruction) {
311 if (!instruction->IsPredicated() &&
312 TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
313 RecordSimplification();
314 } else if (instruction->IsPredicated()) {
315 size_t size = DataType::Size(instruction->GetPackedType());
316 size_t offset = mirror::Array::DataOffset(size).Uint32Value();
317 if (TryExtractArrayAccessAddress(
318 codegen_, instruction, instruction->GetArray(), instruction->GetIndex(), offset)) {
319 RecordSimplification();
320 }
321 }
322 }
323
Run()324 bool InstructionSimplifierArm64::Run() {
325 InstructionSimplifierArm64Visitor visitor(graph_, codegen_, stats_);
326 visitor.VisitReversePostOrder();
327 return true;
328 }
329
330 } // namespace arm64
331 } // namespace art
332