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