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_arm.h"
18
19 #include "code_generator.h"
20 #include "common_arm.h"
21 #include "instruction_simplifier.h"
22 #include "instruction_simplifier_shared.h"
23 #include "mirror/array-inl.h"
24 #include "mirror/string.h"
25 #include "nodes.h"
26
27 namespace art HIDDEN {
28
29 using helpers::CanFitInShifterOperand;
30 using helpers::HasShifterOperand;
31 using helpers::IsSubRightSubLeftShl;
32
33 namespace arm {
34
35 class InstructionSimplifierArmVisitor final : public HGraphVisitor {
36 public:
InstructionSimplifierArmVisitor(HGraph * graph,CodeGenerator * codegen,OptimizingCompilerStats * stats)37 InstructionSimplifierArmVisitor(
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, HInstruction* bitfield_op, 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 void VisitAnd(HAnd* instruction) override;
73 void VisitArrayGet(HArrayGet* instruction) override;
74 void VisitArraySet(HArraySet* instruction) override;
75 void VisitMul(HMul* instruction) override;
76 void VisitOr(HOr* instruction) override;
77 void VisitShl(HShl* instruction) override;
78 void VisitShr(HShr* instruction) override;
79 void VisitSub(HSub* instruction) override;
80 void VisitTypeConversion(HTypeConversion* instruction) override;
81 void VisitUShr(HUShr* instruction) override;
82
83 CodeGenerator* codegen_;
84 OptimizingCompilerStats* stats_;
85 };
86
TryMergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op,bool do_merge)87 bool InstructionSimplifierArmVisitor::TryMergeIntoShifterOperand(HInstruction* use,
88 HInstruction* bitfield_op,
89 bool do_merge) {
90 DCHECK(HasShifterOperand(use, InstructionSet::kArm));
91 DCHECK(use->IsBinaryOperation());
92 DCHECK(CanFitInShifterOperand(bitfield_op));
93 DCHECK(!bitfield_op->HasEnvironmentUses());
94
95 DataType::Type type = use->GetType();
96 if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
97 return false;
98 }
99
100 HInstruction* left = use->InputAt(0);
101 HInstruction* right = use->InputAt(1);
102 DCHECK(left == bitfield_op || right == bitfield_op);
103
104 if (left == right) {
105 // TODO: Handle special transformations in this situation?
106 // For example should we transform `(x << 1) + (x << 1)` into `(x << 2)`?
107 // Or should this be part of a separate transformation logic?
108 return false;
109 }
110
111 bool is_commutative = use->AsBinaryOperation()->IsCommutative();
112 HInstruction* other_input;
113 if (bitfield_op == right) {
114 other_input = left;
115 } else {
116 if (is_commutative) {
117 other_input = right;
118 } else {
119 return false;
120 }
121 }
122
123 HDataProcWithShifterOp::OpKind op_kind;
124 int shift_amount = 0;
125
126 HDataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
127 shift_amount &= use->GetType() == DataType::Type::kInt32
128 ? kMaxIntShiftDistance
129 : kMaxLongShiftDistance;
130
131 if (HDataProcWithShifterOp::IsExtensionOp(op_kind)) {
132 if (!use->IsAdd() && (!use->IsSub() || use->GetType() != DataType::Type::kInt64)) {
133 return false;
134 }
135 // Shift by 1 is a special case that results in the same number and type of instructions
136 // as this simplification, but potentially shorter code.
137 } else if (type == DataType::Type::kInt64 && shift_amount == 1) {
138 return false;
139 }
140
141 if (do_merge) {
142 HDataProcWithShifterOp* alu_with_op =
143 new (GetGraph()->GetAllocator()) HDataProcWithShifterOp(use,
144 other_input,
145 bitfield_op->InputAt(0),
146 op_kind,
147 shift_amount,
148 use->GetDexPc());
149 use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
150 if (bitfield_op->GetUses().empty()) {
151 bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
152 }
153 RecordSimplification();
154 }
155
156 return true;
157 }
158
159 // Merge a bitfield move instruction into its uses if it can be merged in all of them.
TryMergeIntoUsersShifterOperand(HInstruction * bitfield_op)160 bool InstructionSimplifierArmVisitor::TryMergeIntoUsersShifterOperand(HInstruction* bitfield_op) {
161 DCHECK(CanFitInShifterOperand(bitfield_op));
162
163 if (bitfield_op->HasEnvironmentUses()) {
164 return false;
165 }
166
167 const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
168
169 // Check whether we can merge the instruction in all its users' shifter operand.
170 for (const HUseListNode<HInstruction*>& use : uses) {
171 HInstruction* user = use.GetUser();
172 if (!HasShifterOperand(user, InstructionSet::kArm)) {
173 return false;
174 }
175 if (!CanMergeIntoShifterOperand(user, bitfield_op)) {
176 return false;
177 }
178 }
179
180 // Merge the instruction into its uses.
181 for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
182 HInstruction* user = it->GetUser();
183 // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand().
184 ++it;
185 bool merged = MergeIntoShifterOperand(user, bitfield_op);
186 DCHECK(merged);
187 }
188
189 return true;
190 }
191
VisitAnd(HAnd * instruction)192 void InstructionSimplifierArmVisitor::VisitAnd(HAnd* instruction) {
193 if (TryMergeNegatedInput(instruction)) {
194 RecordSimplification();
195 }
196 }
197
VisitArrayGet(HArrayGet * instruction)198 void InstructionSimplifierArmVisitor::VisitArrayGet(HArrayGet* instruction) {
199 size_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
200 DataType::Type type = instruction->GetType();
201
202 // TODO: Implement reading (length + compression) for String compression feature from
203 // negative offset (count_offset - data_offset). Thumb2Assembler (now removed) did
204 // not support T4 encoding of "LDR (immediate)", but ArmVIXLMacroAssembler might.
205 // Don't move array pointer if it is charAt because we need to take the count first.
206 if (mirror::kUseStringCompression && instruction->IsStringCharAt()) {
207 return;
208 }
209
210 // TODO: Support intermediate address for object arrays on arm.
211 if (type == DataType::Type::kReference) {
212 return;
213 }
214
215 if (type == DataType::Type::kInt64
216 || type == DataType::Type::kFloat32
217 || type == DataType::Type::kFloat64) {
218 // T32 doesn't support ShiftedRegOffset mem address mode for these types
219 // to enable optimization.
220 return;
221 }
222
223 if (TryExtractArrayAccessAddress(codegen_,
224 instruction,
225 instruction->GetArray(),
226 instruction->GetIndex(),
227 data_offset)) {
228 RecordSimplification();
229 }
230 }
231
VisitArraySet(HArraySet * instruction)232 void InstructionSimplifierArmVisitor::VisitArraySet(HArraySet* instruction) {
233 size_t access_size = DataType::Size(instruction->GetComponentType());
234 size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value();
235 DataType::Type type = instruction->GetComponentType();
236
237 if (type == DataType::Type::kInt64
238 || type == DataType::Type::kFloat32
239 || type == DataType::Type::kFloat64) {
240 // T32 doesn't support ShiftedRegOffset mem address mode for these types
241 // to enable optimization.
242 return;
243 }
244
245 if (TryExtractArrayAccessAddress(codegen_,
246 instruction,
247 instruction->GetArray(),
248 instruction->GetIndex(),
249 data_offset)) {
250 RecordSimplification();
251 }
252 }
253
VisitMul(HMul * instruction)254 void InstructionSimplifierArmVisitor::VisitMul(HMul* instruction) {
255 if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm)) {
256 RecordSimplification();
257 }
258 }
259
VisitOr(HOr * instruction)260 void InstructionSimplifierArmVisitor::VisitOr(HOr* instruction) {
261 if (TryMergeNegatedInput(instruction)) {
262 RecordSimplification();
263 }
264 }
265
VisitShl(HShl * instruction)266 void InstructionSimplifierArmVisitor::VisitShl(HShl* instruction) {
267 if (instruction->InputAt(1)->IsConstant()) {
268 TryMergeIntoUsersShifterOperand(instruction);
269 }
270 }
271
VisitShr(HShr * instruction)272 void InstructionSimplifierArmVisitor::VisitShr(HShr* instruction) {
273 if (instruction->InputAt(1)->IsConstant()) {
274 TryMergeIntoUsersShifterOperand(instruction);
275 }
276 }
277
VisitSub(HSub * instruction)278 void InstructionSimplifierArmVisitor::VisitSub(HSub* instruction) {
279 if (IsSubRightSubLeftShl(instruction)) {
280 HInstruction* shl = instruction->GetRight()->InputAt(0);
281 if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
282 if (TryMergeIntoUsersShifterOperand(shl)) {
283 return;
284 }
285 }
286 }
287
288 if (TryMergeWithAnd(instruction)) {
289 return;
290 }
291 }
292
VisitTypeConversion(HTypeConversion * instruction)293 void InstructionSimplifierArmVisitor::VisitTypeConversion(HTypeConversion* instruction) {
294 DataType::Type result_type = instruction->GetResultType();
295 DataType::Type input_type = instruction->GetInputType();
296
297 if (input_type == result_type) {
298 // We let the arch-independent code handle this.
299 return;
300 }
301
302 if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) {
303 TryMergeIntoUsersShifterOperand(instruction);
304 }
305 }
306
VisitUShr(HUShr * instruction)307 void InstructionSimplifierArmVisitor::VisitUShr(HUShr* instruction) {
308 if (instruction->InputAt(1)->IsConstant()) {
309 TryMergeIntoUsersShifterOperand(instruction);
310 }
311 }
312
Run()313 bool InstructionSimplifierArm::Run() {
314 InstructionSimplifierArmVisitor visitor(graph_, codegen_, stats_);
315 visitor.VisitReversePostOrder();
316 return true;
317 }
318
319 } // namespace arm
320 } // namespace art
321