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 {
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 : 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->IsStringCharAt()
281       && TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
282     RecordSimplification();
283   }
284 }
285 
VisitVecStore(HVecStore * instruction)286 void InstructionSimplifierArm64Visitor::VisitVecStore(HVecStore* instruction) {
287   if (TryExtractVecArrayAccessAddress(instruction, instruction->GetIndex())) {
288     RecordSimplification();
289   }
290 }
291 
Run()292 bool InstructionSimplifierArm64::Run() {
293   InstructionSimplifierArm64Visitor visitor(graph_, stats_);
294   visitor.VisitReversePostOrder();
295   return true;
296 }
297 
298 }  // namespace arm64
299 }  // namespace art
300