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 VisitShl(HShl* instruction) override;
81   void VisitShr(HShr* instruction) override;
82   void VisitSub(HSub* instruction) override;
83   void VisitTypeConversion(HTypeConversion* instruction) override;
84   void VisitUShr(HUShr* instruction) override;
85   void VisitXor(HXor* instruction) override;
86   void VisitVecLoad(HVecLoad* instruction) override;
87   void VisitVecStore(HVecStore* instruction) override;
88 
89   CodeGenerator* codegen_;
90   OptimizingCompilerStats* stats_;
91 };
92 
TryMergeIntoShifterOperand(HInstruction * use,HInstruction * bitfield_op,bool do_merge)93 bool InstructionSimplifierArm64Visitor::TryMergeIntoShifterOperand(HInstruction* use,
94                                                                    HInstruction* bitfield_op,
95                                                                    bool do_merge) {
96   DCHECK(HasShifterOperand(use, InstructionSet::kArm64));
97   DCHECK(use->IsBinaryOperation() || use->IsNeg());
98   DCHECK(CanFitInShifterOperand(bitfield_op));
99   DCHECK(!bitfield_op->HasEnvironmentUses());
100 
101   DataType::Type type = use->GetType();
102   if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
103     return false;
104   }
105 
106   HInstruction* left;
107   HInstruction* right;
108   if (use->IsBinaryOperation()) {
109     left = use->InputAt(0);
110     right = use->InputAt(1);
111   } else {
112     DCHECK(use->IsNeg());
113     right = use->AsNeg()->InputAt(0);
114     left = GetGraph()->GetConstant(right->GetType(), 0);
115   }
116   DCHECK(left == bitfield_op || right == bitfield_op);
117 
118   if (left == right) {
119     // TODO: Handle special transformations in this situation?
120     // For example should we transform `(x << 1) + (x << 1)` into `(x << 2)`?
121     // Or should this be part of a separate transformation logic?
122     return false;
123   }
124 
125   bool is_commutative = use->IsBinaryOperation() && use->AsBinaryOperation()->IsCommutative();
126   HInstruction* other_input;
127   if (bitfield_op == right) {
128     other_input = left;
129   } else {
130     if (is_commutative) {
131       other_input = right;
132     } else {
133       return false;
134     }
135   }
136 
137   HDataProcWithShifterOp::OpKind op_kind;
138   int shift_amount = 0;
139   HDataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
140 
141   if (HDataProcWithShifterOp::IsExtensionOp(op_kind) && !ShifterOperandSupportsExtension(use)) {
142     return false;
143   }
144 
145   if (do_merge) {
146     HDataProcWithShifterOp* alu_with_op =
147         new (GetGraph()->GetAllocator()) HDataProcWithShifterOp(use,
148                                                                 other_input,
149                                                                 bitfield_op->InputAt(0),
150                                                                 op_kind,
151                                                                 shift_amount,
152                                                                 use->GetDexPc());
153     use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
154     if (bitfield_op->GetUses().empty()) {
155       bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
156     }
157     RecordSimplification();
158   }
159 
160   return true;
161 }
162 
163 // Merge a bitfield move instruction into its uses if it can be merged in all of them.
TryMergeIntoUsersShifterOperand(HInstruction * bitfield_op)164 bool InstructionSimplifierArm64Visitor::TryMergeIntoUsersShifterOperand(HInstruction* bitfield_op) {
165   DCHECK(CanFitInShifterOperand(bitfield_op));
166 
167   if (bitfield_op->HasEnvironmentUses()) {
168     return false;
169   }
170 
171   const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
172 
173   // Check whether we can merge the instruction in all its users' shifter operand.
174   for (const HUseListNode<HInstruction*>& use : uses) {
175     HInstruction* user = use.GetUser();
176     if (!HasShifterOperand(user, InstructionSet::kArm64)) {
177       return false;
178     }
179     if (!CanMergeIntoShifterOperand(user, bitfield_op)) {
180       return false;
181     }
182   }
183 
184   // Merge the instruction into its uses.
185   for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
186     HInstruction* user = it->GetUser();
187     // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand().
188     ++it;
189     bool merged = MergeIntoShifterOperand(user, bitfield_op);
190     DCHECK(merged);
191   }
192 
193   return true;
194 }
195 
VisitAnd(HAnd * instruction)196 void InstructionSimplifierArm64Visitor::VisitAnd(HAnd* instruction) {
197   if (TryMergeNegatedInput(instruction)) {
198     RecordSimplification();
199   }
200 }
201 
VisitArrayGet(HArrayGet * instruction)202 void InstructionSimplifierArm64Visitor::VisitArrayGet(HArrayGet* instruction) {
203   size_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
204   if (TryExtractArrayAccessAddress(codegen_,
205                                    instruction,
206                                    instruction->GetArray(),
207                                    instruction->GetIndex(),
208                                    data_offset)) {
209     RecordSimplification();
210   }
211 }
212 
VisitArraySet(HArraySet * instruction)213 void InstructionSimplifierArm64Visitor::VisitArraySet(HArraySet* instruction) {
214   size_t access_size = DataType::Size(instruction->GetComponentType());
215   size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value();
216   if (TryExtractArrayAccessAddress(codegen_,
217                                    instruction,
218                                    instruction->GetArray(),
219                                    instruction->GetIndex(),
220                                    data_offset)) {
221     RecordSimplification();
222   }
223 }
224 
VisitMul(HMul * instruction)225 void InstructionSimplifierArm64Visitor::VisitMul(HMul* instruction) {
226   if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm64)) {
227     RecordSimplification();
228   }
229 }
230 
VisitOr(HOr * instruction)231 void InstructionSimplifierArm64Visitor::VisitOr(HOr* instruction) {
232   if (TryMergeNegatedInput(instruction)) {
233     RecordSimplification();
234   }
235 }
236 
VisitShl(HShl * instruction)237 void InstructionSimplifierArm64Visitor::VisitShl(HShl* instruction) {
238   if (instruction->InputAt(1)->IsConstant()) {
239     TryMergeIntoUsersShifterOperand(instruction);
240   }
241 }
242 
VisitShr(HShr * instruction)243 void InstructionSimplifierArm64Visitor::VisitShr(HShr* instruction) {
244   if (instruction->InputAt(1)->IsConstant()) {
245     TryMergeIntoUsersShifterOperand(instruction);
246   }
247 }
248 
VisitSub(HSub * instruction)249 void InstructionSimplifierArm64Visitor::VisitSub(HSub* instruction) {
250   if (IsSubRightSubLeftShl(instruction)) {
251     HInstruction* shl = instruction->GetRight()->InputAt(0);
252     if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
253       if (TryMergeIntoUsersShifterOperand(shl)) {
254         return;
255       }
256     }
257   }
258 
259   if (TryMergeWithAnd(instruction)) {
260     return;
261   }
262 }
263 
VisitTypeConversion(HTypeConversion * instruction)264 void InstructionSimplifierArm64Visitor::VisitTypeConversion(HTypeConversion* instruction) {
265   DataType::Type result_type = instruction->GetResultType();
266   DataType::Type input_type = instruction->GetInputType();
267 
268   if (input_type == result_type) {
269     // We let the arch-independent code handle this.
270     return;
271   }
272 
273   if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) {
274     TryMergeIntoUsersShifterOperand(instruction);
275   }
276 }
277 
VisitUShr(HUShr * instruction)278 void InstructionSimplifierArm64Visitor::VisitUShr(HUShr* instruction) {
279   if (instruction->InputAt(1)->IsConstant()) {
280     TryMergeIntoUsersShifterOperand(instruction);
281   }
282 }
283 
VisitXor(HXor * instruction)284 void InstructionSimplifierArm64Visitor::VisitXor(HXor* instruction) {
285   if (TryMergeNegatedInput(instruction)) {
286     RecordSimplification();
287   }
288 }
289 
VisitVecLoad(HVecLoad * instruction)290 void InstructionSimplifierArm64Visitor::VisitVecLoad(HVecLoad* instruction) {
291   if (!instruction->IsPredicated() && !instruction->IsStringCharAt() &&
292       TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
293     RecordSimplification();
294   } else if (instruction->IsPredicated()) {
295     size_t size = DataType::Size(instruction->GetPackedType());
296     size_t offset = mirror::Array::DataOffset(size).Uint32Value();
297     if (TryExtractArrayAccessAddress(
298             codegen_, instruction, instruction->GetArray(), instruction->GetIndex(), offset)) {
299       RecordSimplification();
300     }
301   }
302 }
303 
VisitVecStore(HVecStore * instruction)304 void InstructionSimplifierArm64Visitor::VisitVecStore(HVecStore* instruction) {
305   if (!instruction->IsPredicated() &&
306       TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
307     RecordSimplification();
308   } else if (instruction->IsPredicated()) {
309     size_t size = DataType::Size(instruction->GetPackedType());
310     size_t offset = mirror::Array::DataOffset(size).Uint32Value();
311     if (TryExtractArrayAccessAddress(
312             codegen_, instruction, instruction->GetArray(), instruction->GetIndex(), offset)) {
313       RecordSimplification();
314     }
315   }
316 }
317 
Run()318 bool InstructionSimplifierArm64::Run() {
319   InstructionSimplifierArm64Visitor visitor(graph_, codegen_, stats_);
320   visitor.VisitReversePostOrder();
321   return true;
322 }
323 
324 }  // namespace arm64
325 }  // namespace art
326