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_shared.h"
18
19namespace art {
20
21namespace {
22
23bool TrySimpleMultiplyAccumulatePatterns(HMul* mul,
24                                         HBinaryOperation* input_binop,
25                                         HInstruction* input_other) {
26  DCHECK(Primitive::IsIntOrLongType(mul->GetType()));
27  DCHECK(input_binop->IsAdd() || input_binop->IsSub());
28  DCHECK_NE(input_binop, input_other);
29  if (!input_binop->HasOnlyOneNonEnvironmentUse()) {
30    return false;
31  }
32
33  // Try to interpret patterns like
34  //    a * (b <+/-> 1)
35  // as
36  //    (a * b) <+/-> a
37  HInstruction* input_a = input_other;
38  HInstruction* input_b = nullptr;  // Set to a non-null value if we found a pattern to optimize.
39  HInstruction::InstructionKind op_kind;
40
41  if (input_binop->IsAdd()) {
42    if ((input_binop->GetConstantRight() != nullptr) && input_binop->GetConstantRight()->IsOne()) {
43      // Interpret
44      //    a * (b + 1)
45      // as
46      //    (a * b) + a
47      input_b = input_binop->GetLeastConstantLeft();
48      op_kind = HInstruction::kAdd;
49    }
50  } else {
51    DCHECK(input_binop->IsSub());
52    if (input_binop->GetRight()->IsConstant() &&
53        input_binop->GetRight()->AsConstant()->IsMinusOne()) {
54      // Interpret
55      //    a * (b - (-1))
56      // as
57      //    a + (a * b)
58      input_b = input_binop->GetLeft();
59      op_kind = HInstruction::kAdd;
60    } else if (input_binop->GetLeft()->IsConstant() &&
61               input_binop->GetLeft()->AsConstant()->IsOne()) {
62      // Interpret
63      //    a * (1 - b)
64      // as
65      //    a - (a * b)
66      input_b = input_binop->GetRight();
67      op_kind = HInstruction::kSub;
68    }
69  }
70
71  if (input_b == nullptr) {
72    // We did not find a pattern we can optimize.
73    return false;
74  }
75
76  ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena();
77  HMultiplyAccumulate* mulacc = new(arena) HMultiplyAccumulate(
78      mul->GetType(), op_kind, input_a, input_a, input_b, mul->GetDexPc());
79
80  mul->GetBlock()->ReplaceAndRemoveInstructionWith(mul, mulacc);
81  input_binop->GetBlock()->RemoveInstruction(input_binop);
82
83  return true;
84}
85
86}  // namespace
87
88bool TryCombineMultiplyAccumulate(HMul* mul, InstructionSet isa) {
89  Primitive::Type type = mul->GetType();
90  switch (isa) {
91    case kArm:
92    case kThumb2:
93      if (type != Primitive::kPrimInt) {
94        return false;
95      }
96      break;
97    case kArm64:
98      if (!Primitive::IsIntOrLongType(type)) {
99        return false;
100      }
101      break;
102    default:
103      return false;
104  }
105
106  ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena();
107
108  if (mul->HasOnlyOneNonEnvironmentUse()) {
109    HInstruction* use = mul->GetUses().front().GetUser();
110    if (use->IsAdd() || use->IsSub()) {
111      // Replace code looking like
112      //    MUL tmp, x, y
113      //    SUB dst, acc, tmp
114      // with
115      //    MULSUB dst, acc, x, y
116      // Note that we do not want to (unconditionally) perform the merge when the
117      // multiplication has multiple uses and it can be merged in all of them.
118      // Multiple uses could happen on the same control-flow path, and we would
119      // then increase the amount of work. In the future we could try to evaluate
120      // whether all uses are on different control-flow paths (using dominance and
121      // reverse-dominance information) and only perform the merge when they are.
122      HInstruction* accumulator = nullptr;
123      HBinaryOperation* binop = use->AsBinaryOperation();
124      HInstruction* binop_left = binop->GetLeft();
125      HInstruction* binop_right = binop->GetRight();
126      // Be careful after GVN. This should not happen since the `HMul` has only
127      // one use.
128      DCHECK_NE(binop_left, binop_right);
129      if (binop_right == mul) {
130        accumulator = binop_left;
131      } else if (use->IsAdd()) {
132        DCHECK_EQ(binop_left, mul);
133        accumulator = binop_right;
134      }
135
136      if (accumulator != nullptr) {
137        HMultiplyAccumulate* mulacc =
138            new (arena) HMultiplyAccumulate(type,
139                                            binop->GetKind(),
140                                            accumulator,
141                                            mul->GetLeft(),
142                                            mul->GetRight());
143
144        binop->GetBlock()->ReplaceAndRemoveInstructionWith(binop, mulacc);
145        DCHECK(!mul->HasUses());
146        mul->GetBlock()->RemoveInstruction(mul);
147        return true;
148      }
149    } else if (use->IsNeg() && isa != kArm) {
150      HMultiplyAccumulate* mulacc =
151          new (arena) HMultiplyAccumulate(type,
152                                          HInstruction::kSub,
153                                          mul->GetBlock()->GetGraph()->GetConstant(type, 0),
154                                          mul->GetLeft(),
155                                          mul->GetRight());
156
157      use->GetBlock()->ReplaceAndRemoveInstructionWith(use, mulacc);
158      DCHECK(!mul->HasUses());
159      mul->GetBlock()->RemoveInstruction(mul);
160      return true;
161    }
162  }
163
164  // Use multiply accumulate instruction for a few simple patterns.
165  // We prefer not applying the following transformations if the left and
166  // right inputs perform the same operation.
167  // We rely on GVN having squashed the inputs if appropriate. However the
168  // results are still correct even if that did not happen.
169  if (mul->GetLeft() == mul->GetRight()) {
170    return false;
171  }
172
173  HInstruction* left = mul->GetLeft();
174  HInstruction* right = mul->GetRight();
175  if ((right->IsAdd() || right->IsSub()) &&
176      TrySimpleMultiplyAccumulatePatterns(mul, right->AsBinaryOperation(), left)) {
177    return true;
178  }
179  if ((left->IsAdd() || left->IsSub()) &&
180      TrySimpleMultiplyAccumulatePatterns(mul, left->AsBinaryOperation(), right)) {
181    return true;
182  }
183  return false;
184}
185
186
187bool TryMergeNegatedInput(HBinaryOperation* op) {
188  DCHECK(op->IsAnd() || op->IsOr() || op->IsXor()) << op->DebugName();
189  HInstruction* left = op->GetLeft();
190  HInstruction* right = op->GetRight();
191
192  // Only consider the case where there is exactly one Not, with 2 Not's De
193  // Morgan's laws should be applied instead.
194  if (left->IsNot() ^ right->IsNot()) {
195    HInstruction* hnot = (left->IsNot() ? left : right);
196    HInstruction* hother = (left->IsNot() ? right : left);
197
198    // Only do the simplification if the Not has only one use and can thus be
199    // safely removed. Even though ARM64 negated bitwise operations do not have
200    // an immediate variant (only register), we still do the simplification when
201    // `hother` is a constant, because it removes an instruction if the constant
202    // cannot be encoded as an immediate:
203    //   mov r0, #large_constant
204    //   neg r2, r1
205    //   and r0, r0, r2
206    // becomes:
207    //   mov r0, #large_constant
208    //   bic r0, r0, r1
209    if (hnot->HasOnlyOneNonEnvironmentUse()) {
210      // Replace code looking like
211      //    NOT tmp, mask
212      //    AND dst, src, tmp   (respectively ORR, EOR)
213      // with
214      //    BIC dst, src, mask  (respectively ORN, EON)
215      HInstruction* src = hnot->AsNot()->GetInput();
216
217      HBitwiseNegatedRight* neg_op = new (hnot->GetBlock()->GetGraph()->GetArena())
218          HBitwiseNegatedRight(op->GetType(), op->GetKind(), hother, src, op->GetDexPc());
219
220      op->GetBlock()->ReplaceAndRemoveInstructionWith(op, neg_op);
221      hnot->GetBlock()->RemoveInstruction(hnot);
222      return true;
223    }
224  }
225
226  return false;
227}
228
229
230bool TryExtractArrayAccessAddress(HInstruction* access,
231                                  HInstruction* array,
232                                  HInstruction* index,
233                                  size_t data_offset) {
234  if (index->IsConstant() ||
235      (index->IsBoundsCheck() && index->AsBoundsCheck()->GetIndex()->IsConstant())) {
236    // When the index is a constant all the addressing can be fitted in the
237    // memory access instruction, so do not split the access.
238    return false;
239  }
240  if (access->IsArraySet() &&
241      access->AsArraySet()->GetValue()->GetType() == Primitive::kPrimNot) {
242    // The access may require a runtime call or the original array pointer.
243    return false;
244  }
245  if (kEmitCompilerReadBarrier &&
246      access->IsArrayGet() &&
247      access->GetType() == Primitive::kPrimNot) {
248    // For object arrays, the read barrier instrumentation requires
249    // the original array pointer.
250    return false;
251  }
252
253  // Proceed to extract the base address computation.
254  HGraph* graph = access->GetBlock()->GetGraph();
255  ArenaAllocator* arena = graph->GetArena();
256
257  HIntConstant* offset = graph->GetIntConstant(data_offset);
258  HIntermediateAddress* address = new (arena) HIntermediateAddress(array, offset, kNoDexPc);
259  // TODO: Is it ok to not have this on the intermediate address?
260  // address->SetReferenceTypeInfo(array->GetReferenceTypeInfo());
261  access->GetBlock()->InsertInstructionBefore(address, access);
262  access->ReplaceInput(address, 0);
263  // Both instructions must depend on GC to prevent any instruction that can
264  // trigger GC to be inserted between the two.
265  access->AddSideEffects(SideEffects::DependsOnGC());
266  DCHECK(address->GetSideEffects().Includes(SideEffects::DependsOnGC()));
267  DCHECK(access->GetSideEffects().Includes(SideEffects::DependsOnGC()));
268  // TODO: Code generation for HArrayGet and HArraySet will check whether the input address
269  // is an HIntermediateAddress and generate appropriate code.
270  // We would like to replace the `HArrayGet` and `HArraySet` with custom instructions (maybe
271  // `HArm64Load` and `HArm64Store`,`HArmLoad` and `HArmStore`). We defer these changes
272  // because these new instructions would not bring any advantages yet.
273  // Also see the comments in
274  // `InstructionCodeGeneratorARM::VisitArrayGet()`
275  // `InstructionCodeGeneratorARM::VisitArraySet()`
276  // `InstructionCodeGeneratorARM64::VisitArrayGet()`
277  // `InstructionCodeGeneratorARM64::VisitArraySet()`.
278  return true;
279}
280
281bool TryCombineVecMultiplyAccumulate(HVecMul* mul, InstructionSet isa) {
282  Primitive::Type type = mul->GetPackedType();
283  switch (isa) {
284    case kArm64:
285      if (!(type == Primitive::kPrimByte ||
286            type == Primitive::kPrimChar ||
287            type == Primitive::kPrimShort ||
288            type == Primitive::kPrimInt)) {
289        return false;
290      }
291      break;
292    default:
293      return false;
294  }
295
296  ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena();
297
298  if (mul->HasOnlyOneNonEnvironmentUse()) {
299    HInstruction* use = mul->GetUses().front().GetUser();
300    if (use->IsVecAdd() || use->IsVecSub()) {
301      // Replace code looking like
302      //    VECMUL tmp, x, y
303      //    VECADD/SUB dst, acc, tmp
304      // with
305      //    VECMULACC dst, acc, x, y
306      // Note that we do not want to (unconditionally) perform the merge when the
307      // multiplication has multiple uses and it can be merged in all of them.
308      // Multiple uses could happen on the same control-flow path, and we would
309      // then increase the amount of work. In the future we could try to evaluate
310      // whether all uses are on different control-flow paths (using dominance and
311      // reverse-dominance information) and only perform the merge when they are.
312      HInstruction* accumulator = nullptr;
313      HVecBinaryOperation* binop = use->AsVecBinaryOperation();
314      HInstruction* binop_left = binop->GetLeft();
315      HInstruction* binop_right = binop->GetRight();
316      // This is always true since the `HVecMul` has only one use (which is checked above).
317      DCHECK_NE(binop_left, binop_right);
318      if (binop_right == mul) {
319        accumulator = binop_left;
320      } else if (use->IsVecAdd()) {
321        DCHECK_EQ(binop_left, mul);
322        accumulator = binop_right;
323      }
324
325      HInstruction::InstructionKind kind =
326          use->IsVecAdd() ? HInstruction::kAdd : HInstruction::kSub;
327      if (accumulator != nullptr) {
328        HVecMultiplyAccumulate* mulacc =
329            new (arena) HVecMultiplyAccumulate(arena,
330                                               kind,
331                                               accumulator,
332                                               mul->GetLeft(),
333                                               mul->GetRight(),
334                                               binop->GetPackedType(),
335                                               binop->GetVectorLength());
336
337        binop->GetBlock()->ReplaceAndRemoveInstructionWith(binop, mulacc);
338        DCHECK(!mul->HasUses());
339        mul->GetBlock()->RemoveInstruction(mul);
340        return true;
341      }
342    }
343  }
344
345  return false;
346}
347
348}  // namespace art
349