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