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