instruction_simplifier_arm64.cc revision 6b5afdd144d2bb3bf994240797834b5666b2cf98 
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 "mirror/array-inl.h"
21
22namespace art {
23namespace arm64 {
24
25using helpers::CanFitInShifterOperand;
26using helpers::HasShifterOperand;
27using helpers::ShifterOperandSupportsExtension;
28
29void InstructionSimplifierArm64Visitor::TryExtractArrayAccessAddress(HInstruction* access,
30                                                                     HInstruction* array,
31                                                                     HInstruction* index,
32                                                                     int access_size) {
33  if (kEmitCompilerReadBarrier) {
34    // The read barrier instrumentation does not support the
35    // HArm64IntermediateAddress instruction yet.
36    //
37    // TODO: Handle this case properly in the ARM64 code generator and
38    // re-enable this optimization; otherwise, remove this TODO.
39    // b/26601270
40    return;
41  }
42  if (index->IsConstant() ||
43      (index->IsBoundsCheck() && index->AsBoundsCheck()->GetIndex()->IsConstant())) {
44    // When the index is a constant all the addressing can be fitted in the
45    // memory access instruction, so do not split the access.
46    return;
47  }
48  if (access->IsArraySet() &&
49      access->AsArraySet()->GetValue()->GetType() == Primitive::kPrimNot) {
50    // The access may require a runtime call or the original array pointer.
51    return;
52  }
53
54  // Proceed to extract the base address computation.
55  ArenaAllocator* arena = GetGraph()->GetArena();
56
57  HIntConstant* offset =
58      GetGraph()->GetIntConstant(mirror::Array::DataOffset(access_size).Uint32Value());
59  HArm64IntermediateAddress* address =
60      new (arena) HArm64IntermediateAddress(array, offset, kNoDexPc);
61  address->SetReferenceTypeInfo(array->GetReferenceTypeInfo());
62  access->GetBlock()->InsertInstructionBefore(address, access);
63  access->ReplaceInput(address, 0);
64  // Both instructions must depend on GC to prevent any instruction that can
65  // trigger GC to be inserted between the two.
66  access->AddSideEffects(SideEffects::DependsOnGC());
67  DCHECK(address->GetSideEffects().Includes(SideEffects::DependsOnGC()));
68  DCHECK(access->GetSideEffects().Includes(SideEffects::DependsOnGC()));
69  // TODO: Code generation for HArrayGet and HArraySet will check whether the input address
70  // is an HArm64IntermediateAddress and generate appropriate code.
71  // We would like to replace the `HArrayGet` and `HArraySet` with custom instructions (maybe
72  // `HArm64Load` and `HArm64Store`). We defer these changes because these new instructions would
73  // not bring any advantages yet.
74  // Also see the comments in
75  // `InstructionCodeGeneratorARM64::VisitArrayGet()` and
76  // `InstructionCodeGeneratorARM64::VisitArraySet()`.
77  RecordSimplification();
78}
79
80bool InstructionSimplifierArm64Visitor::TryMergeIntoShifterOperand(HInstruction* use,
81                                                                   HInstruction* bitfield_op,
82                                                                   bool do_merge) {
83  DCHECK(HasShifterOperand(use));
84  DCHECK(use->IsBinaryOperation() || use->IsNeg());
85  DCHECK(CanFitInShifterOperand(bitfield_op));
86  DCHECK(!bitfield_op->HasEnvironmentUses());
87
88  Primitive::Type type = use->GetType();
89  if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) {
90    return false;
91  }
92
93  HInstruction* left;
94  HInstruction* right;
95  if (use->IsBinaryOperation()) {
96    left = use->InputAt(0);
97    right = use->InputAt(1);
98  } else {
99    DCHECK(use->IsNeg());
100    right = use->AsNeg()->InputAt(0);
101    left = GetGraph()->GetConstant(right->GetType(), 0);
102  }
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->IsBinaryOperation() && 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  HArm64DataProcWithShifterOp::OpKind op_kind;
125  int shift_amount = 0;
126  HArm64DataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
127
128  if (HArm64DataProcWithShifterOp::IsExtensionOp(op_kind) &&
129      !ShifterOperandSupportsExtension(use)) {
130    return false;
131  }
132
133  if (do_merge) {
134    HArm64DataProcWithShifterOp* alu_with_op =
135        new (GetGraph()->GetArena()) HArm64DataProcWithShifterOp(use,
136                                                                 other_input,
137                                                                 bitfield_op->InputAt(0),
138                                                                 op_kind,
139                                                                 shift_amount,
140                                                                 use->GetDexPc());
141    use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
142    if (bitfield_op->GetUses().IsEmpty()) {
143      bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
144    }
145    RecordSimplification();
146  }
147
148  return true;
149}
150
151// Merge a bitfield move instruction into its uses if it can be merged in all of them.
152bool InstructionSimplifierArm64Visitor::TryMergeIntoUsersShifterOperand(HInstruction* bitfield_op) {
153  DCHECK(CanFitInShifterOperand(bitfield_op));
154
155  if (bitfield_op->HasEnvironmentUses()) {
156    return false;
157  }
158
159  const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
160
161  // Check whether we can merge the instruction in all its users' shifter operand.
162  for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) {
163    HInstruction* use = it_use.Current()->GetUser();
164    if (!HasShifterOperand(use)) {
165      return false;
166    }
167    if (!CanMergeIntoShifterOperand(use, bitfield_op)) {
168      return false;
169    }
170  }
171
172  // Merge the instruction into its uses.
173  for (HUseIterator<HInstruction*> it_use(uses); !it_use.Done(); it_use.Advance()) {
174    HInstruction* use = it_use.Current()->GetUser();
175    bool merged = MergeIntoShifterOperand(use, bitfield_op);
176    DCHECK(merged);
177  }
178
179  return true;
180}
181
182bool InstructionSimplifierArm64Visitor::TrySimpleMultiplyAccumulatePatterns(
183    HMul* mul, HBinaryOperation* input_binop, HInstruction* input_other) {
184  DCHECK(Primitive::IsIntOrLongType(mul->GetType()));
185  DCHECK(input_binop->IsAdd() || input_binop->IsSub());
186  DCHECK_NE(input_binop, input_other);
187  if (!input_binop->HasOnlyOneNonEnvironmentUse()) {
188    return false;
189  }
190
191  // Try to interpret patterns like
192  //    a * (b <+/-> 1)
193  // as
194  //    (a * b) <+/-> a
195  HInstruction* input_a = input_other;
196  HInstruction* input_b = nullptr;  // Set to a non-null value if we found a pattern to optimize.
197  HInstruction::InstructionKind op_kind;
198
199  if (input_binop->IsAdd()) {
200    if ((input_binop->GetConstantRight() != nullptr) && input_binop->GetConstantRight()->IsOne()) {
201      // Interpret
202      //    a * (b + 1)
203      // as
204      //    (a * b) + a
205      input_b = input_binop->GetLeastConstantLeft();
206      op_kind = HInstruction::kAdd;
207    }
208  } else {
209    DCHECK(input_binop->IsSub());
210    if (input_binop->GetRight()->IsConstant() &&
211        input_binop->GetRight()->AsConstant()->IsMinusOne()) {
212      // Interpret
213      //    a * (b - (-1))
214      // as
215      //    a + (a * b)
216      input_b = input_binop->GetLeft();
217      op_kind = HInstruction::kAdd;
218    } else if (input_binop->GetLeft()->IsConstant() &&
219               input_binop->GetLeft()->AsConstant()->IsOne()) {
220      // Interpret
221      //    a * (1 - b)
222      // as
223      //    a - (a * b)
224      input_b = input_binop->GetRight();
225      op_kind = HInstruction::kSub;
226    }
227  }
228
229  if (input_b == nullptr) {
230    // We did not find a pattern we can optimize.
231    return false;
232  }
233
234  HArm64MultiplyAccumulate* mulacc = new(GetGraph()->GetArena()) HArm64MultiplyAccumulate(
235      mul->GetType(), op_kind, input_a, input_a, input_b, mul->GetDexPc());
236
237  mul->GetBlock()->ReplaceAndRemoveInstructionWith(mul, mulacc);
238  input_binop->GetBlock()->RemoveInstruction(input_binop);
239
240  return false;
241}
242
243void InstructionSimplifierArm64Visitor::VisitArrayGet(HArrayGet* instruction) {
244  TryExtractArrayAccessAddress(instruction,
245                               instruction->GetArray(),
246                               instruction->GetIndex(),
247                               Primitive::ComponentSize(instruction->GetType()));
248}
249
250void InstructionSimplifierArm64Visitor::VisitArraySet(HArraySet* instruction) {
251  TryExtractArrayAccessAddress(instruction,
252                               instruction->GetArray(),
253                               instruction->GetIndex(),
254                               Primitive::ComponentSize(instruction->GetComponentType()));
255}
256
257void InstructionSimplifierArm64Visitor::VisitMul(HMul* instruction) {
258  Primitive::Type type = instruction->GetType();
259  if (!Primitive::IsIntOrLongType(type)) {
260    return;
261  }
262
263  HInstruction* use = instruction->HasNonEnvironmentUses()
264      ? instruction->GetUses().GetFirst()->GetUser()
265      : nullptr;
266
267  if (instruction->HasOnlyOneNonEnvironmentUse() && (use->IsAdd() || use->IsSub())) {
268    // Replace code looking like
269    //    MUL tmp, x, y
270    //    SUB dst, acc, tmp
271    // with
272    //    MULSUB dst, acc, x, y
273    // Note that we do not want to (unconditionally) perform the merge when the
274    // multiplication has multiple uses and it can be merged in all of them.
275    // Multiple uses could happen on the same control-flow path, and we would
276    // then increase the amount of work. In the future we could try to evaluate
277    // whether all uses are on different control-flow paths (using dominance and
278    // reverse-dominance information) and only perform the merge when they are.
279    HInstruction* accumulator = nullptr;
280    HBinaryOperation* binop = use->AsBinaryOperation();
281    HInstruction* binop_left = binop->GetLeft();
282    HInstruction* binop_right = binop->GetRight();
283    // Be careful after GVN. This should not happen since the `HMul` has only
284    // one use.
285    DCHECK_NE(binop_left, binop_right);
286    if (binop_right == instruction) {
287      accumulator = binop_left;
288    } else if (use->IsAdd()) {
289      DCHECK_EQ(binop_left, instruction);
290      accumulator = binop_right;
291    }
292
293    if (accumulator != nullptr) {
294      HArm64MultiplyAccumulate* mulacc =
295          new (GetGraph()->GetArena()) HArm64MultiplyAccumulate(type,
296                                                                binop->GetKind(),
297                                                                accumulator,
298                                                                instruction->GetLeft(),
299                                                                instruction->GetRight());
300
301      binop->GetBlock()->ReplaceAndRemoveInstructionWith(binop, mulacc);
302      DCHECK(!instruction->HasUses());
303      instruction->GetBlock()->RemoveInstruction(instruction);
304      RecordSimplification();
305      return;
306    }
307  }
308
309  // Use multiply accumulate instruction for a few simple patterns.
310  // We prefer not applying the following transformations if the left and
311  // right inputs perform the same operation.
312  // We rely on GVN having squashed the inputs if appropriate. However the
313  // results are still correct even if that did not happen.
314  if (instruction->GetLeft() == instruction->GetRight()) {
315    return;
316  }
317
318  HInstruction* left = instruction->GetLeft();
319  HInstruction* right = instruction->GetRight();
320  if ((right->IsAdd() || right->IsSub()) &&
321      TrySimpleMultiplyAccumulatePatterns(instruction, right->AsBinaryOperation(), left)) {
322    return;
323  }
324  if ((left->IsAdd() || left->IsSub()) &&
325      TrySimpleMultiplyAccumulatePatterns(instruction, left->AsBinaryOperation(), right)) {
326    return;
327  }
328}
329
330void InstructionSimplifierArm64Visitor::VisitShl(HShl* instruction) {
331  if (instruction->InputAt(1)->IsConstant()) {
332    TryMergeIntoUsersShifterOperand(instruction);
333  }
334}
335
336void InstructionSimplifierArm64Visitor::VisitShr(HShr* instruction) {
337  if (instruction->InputAt(1)->IsConstant()) {
338    TryMergeIntoUsersShifterOperand(instruction);
339  }
340}
341
342void InstructionSimplifierArm64Visitor::VisitTypeConversion(HTypeConversion* instruction) {
343  Primitive::Type result_type = instruction->GetResultType();
344  Primitive::Type input_type = instruction->GetInputType();
345
346  if (input_type == result_type) {
347    // We let the arch-independent code handle this.
348    return;
349  }
350
351  if (Primitive::IsIntegralType(result_type) && Primitive::IsIntegralType(input_type)) {
352    TryMergeIntoUsersShifterOperand(instruction);
353  }
354}
355
356void InstructionSimplifierArm64Visitor::VisitUShr(HUShr* instruction) {
357  if (instruction->InputAt(1)->IsConstant()) {
358    TryMergeIntoUsersShifterOperand(instruction);
359  }
360}
361
362}  // namespace arm64
363}  // namespace art
364