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 VisitRol(HRol* 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
84 CodeGenerator* codegen_;
85 OptimizingCompilerStats* stats_;
86 };
87
TryMergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op,bool do_merge)88 bool InstructionSimplifierArmVisitor::TryMergeIntoShifterOperand(HInstruction* use,
89 HInstruction* bitfield_op,
90 bool do_merge) {
91 DCHECK(HasShifterOperand(use, InstructionSet::kArm));
92 DCHECK(use->IsBinaryOperation());
93 DCHECK(CanFitInShifterOperand(bitfield_op));
94 DCHECK(!bitfield_op->HasEnvironmentUses());
95
96 DataType::Type type = use->GetType();
97 if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
98 return false;
99 }
100
101 HInstruction* left = use->InputAt(0);
102 HInstruction* right = use->InputAt(1);
103 DCHECK(left == bitfield_op || right == bitfield_op);
104
105 if (left == right) {
106 // TODO: Handle special transformations in this situation?
107 // For example should we transform `(x << 1) + (x << 1)` into `(x << 2)`?
108 // Or should this be part of a separate transformation logic?
109 return false;
110 }
111
112 bool is_commutative = use->AsBinaryOperation()->IsCommutative();
113 HInstruction* other_input;
114 if (bitfield_op == right) {
115 other_input = left;
116 } else {
117 if (is_commutative) {
118 other_input = right;
119 } else {
120 return false;
121 }
122 }
123
124 HDataProcWithShifterOp::OpKind op_kind;
125 int shift_amount = 0;
126
127 HDataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
128 shift_amount &= use->GetType() == DataType::Type::kInt32
129 ? kMaxIntShiftDistance
130 : kMaxLongShiftDistance;
131
132 if (HDataProcWithShifterOp::IsExtensionOp(op_kind)) {
133 if (!use->IsAdd() && (!use->IsSub() || use->GetType() != DataType::Type::kInt64)) {
134 return false;
135 }
136 // Shift by 1 is a special case that results in the same number and type of instructions
137 // as this simplification, but potentially shorter code.
138 } else if (type == DataType::Type::kInt64 && shift_amount == 1) {
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 InstructionSimplifierArmVisitor::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::kArm)) {
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 InstructionSimplifierArmVisitor::VisitAnd(HAnd* instruction) {
194 if (TryMergeNegatedInput(instruction)) {
195 RecordSimplification();
196 }
197 }
198
VisitArrayGet(HArrayGet * instruction)199 void InstructionSimplifierArmVisitor::VisitArrayGet(HArrayGet* instruction) {
200 size_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
201 DataType::Type type = instruction->GetType();
202
203 // TODO: Implement reading (length + compression) for String compression feature from
204 // negative offset (count_offset - data_offset). Thumb2Assembler (now removed) did
205 // not support T4 encoding of "LDR (immediate)", but ArmVIXLMacroAssembler might.
206 // Don't move array pointer if it is charAt because we need to take the count first.
207 if (mirror::kUseStringCompression && instruction->IsStringCharAt()) {
208 return;
209 }
210
211 // TODO: Support intermediate address for object arrays on arm.
212 if (type == DataType::Type::kReference) {
213 return;
214 }
215
216 if (type == DataType::Type::kInt64
217 || type == DataType::Type::kFloat32
218 || type == DataType::Type::kFloat64) {
219 // T32 doesn't support ShiftedRegOffset mem address mode for these types
220 // to enable optimization.
221 return;
222 }
223
224 if (TryExtractArrayAccessAddress(codegen_,
225 instruction,
226 instruction->GetArray(),
227 instruction->GetIndex(),
228 data_offset)) {
229 RecordSimplification();
230 }
231 }
232
VisitArraySet(HArraySet * instruction)233 void InstructionSimplifierArmVisitor::VisitArraySet(HArraySet* instruction) {
234 size_t access_size = DataType::Size(instruction->GetComponentType());
235 size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value();
236 DataType::Type type = instruction->GetComponentType();
237
238 if (type == DataType::Type::kInt64
239 || type == DataType::Type::kFloat32
240 || type == DataType::Type::kFloat64) {
241 // T32 doesn't support ShiftedRegOffset mem address mode for these types
242 // to enable optimization.
243 return;
244 }
245
246 if (TryExtractArrayAccessAddress(codegen_,
247 instruction,
248 instruction->GetArray(),
249 instruction->GetIndex(),
250 data_offset)) {
251 RecordSimplification();
252 }
253 }
254
VisitMul(HMul * instruction)255 void InstructionSimplifierArmVisitor::VisitMul(HMul* instruction) {
256 if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm)) {
257 RecordSimplification();
258 }
259 }
260
VisitOr(HOr * instruction)261 void InstructionSimplifierArmVisitor::VisitOr(HOr* instruction) {
262 if (TryMergeNegatedInput(instruction)) {
263 RecordSimplification();
264 }
265 }
266
VisitRol(HRol * instruction)267 void InstructionSimplifierArmVisitor::VisitRol(HRol* instruction) {
268 UnfoldRotateLeft(instruction);
269 RecordSimplification();
270 }
271
VisitShl(HShl * instruction)272 void InstructionSimplifierArmVisitor::VisitShl(HShl* instruction) {
273 if (instruction->InputAt(1)->IsConstant()) {
274 TryMergeIntoUsersShifterOperand(instruction);
275 }
276 }
277
VisitShr(HShr * instruction)278 void InstructionSimplifierArmVisitor::VisitShr(HShr* instruction) {
279 if (instruction->InputAt(1)->IsConstant()) {
280 TryMergeIntoUsersShifterOperand(instruction);
281 }
282 }
283
VisitSub(HSub * instruction)284 void InstructionSimplifierArmVisitor::VisitSub(HSub* instruction) {
285 if (IsSubRightSubLeftShl(instruction)) {
286 HInstruction* shl = instruction->GetRight()->InputAt(0);
287 if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
288 if (TryMergeIntoUsersShifterOperand(shl)) {
289 return;
290 }
291 }
292 }
293
294 if (TryMergeWithAnd(instruction)) {
295 return;
296 }
297 }
298
VisitTypeConversion(HTypeConversion * instruction)299 void InstructionSimplifierArmVisitor::VisitTypeConversion(HTypeConversion* instruction) {
300 DataType::Type result_type = instruction->GetResultType();
301 DataType::Type input_type = instruction->GetInputType();
302
303 if (input_type == result_type) {
304 // We let the arch-independent code handle this.
305 return;
306 }
307
308 if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) {
309 TryMergeIntoUsersShifterOperand(instruction);
310 }
311 }
312
VisitUShr(HUShr * instruction)313 void InstructionSimplifierArmVisitor::VisitUShr(HUShr* instruction) {
314 if (instruction->InputAt(1)->IsConstant()) {
315 TryMergeIntoUsersShifterOperand(instruction);
316 }
317 }
318
Run()319 bool InstructionSimplifierArm::Run() {
320 InstructionSimplifierArmVisitor visitor(graph_, codegen_, stats_);
321 visitor.VisitReversePostOrder();
322 return true;
323 }
324
325 } // namespace arm
326 } // namespace art
327