Artem Udovichenko | 4a0dad6 | 2016-01-26 12:28:31 +0300 | [diff] [blame] | 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 | |
| 19 | namespace art { |
| 20 | |
| 21 | namespace { |
| 22 | |
| 23 | bool 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 | |
| 88 | bool 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 | |
Artem Udovichenko | 4a0dad6 | 2016-01-26 12:28:31 +0300 | [diff] [blame] | 106 | ArenaAllocator* arena = mul->GetBlock()->GetGraph()->GetArena(); |
| 107 | |
| 108 | if (mul->HasOnlyOneNonEnvironmentUse()) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 109 | HInstruction* use = mul->GetUses().front().GetUser(); |
Artem Udovichenko | 4a0dad6 | 2016-01-26 12:28:31 +0300 | [diff] [blame] | 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 | |
Artem Serov | 7fc6350 | 2016-02-09 17:15:29 +0000 | [diff] [blame] | 186 | |
| 187 | bool 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 | |
Artem Serov | 328429f | 2016-07-06 16:23:04 +0100 | [diff] [blame] | 229 | |
| 230 | bool TryExtractArrayAccessAddress(HInstruction* access, |
| 231 | HInstruction* array, |
| 232 | HInstruction* index, |
| 233 | size_t data_offset) { |
Artem Serov | 328429f | 2016-07-06 16:23:04 +0100 | [diff] [blame] | 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 | } |
Roland Levillain | 19c5419 | 2016-11-04 13:44:09 +0000 | [diff] [blame] | 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 | } |
Artem Serov | 328429f | 2016-07-06 16:23:04 +0100 | [diff] [blame] | 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); |
Roland Levillain | 19c5419 | 2016-11-04 13:44:09 +0000 | [diff] [blame] | 258 | HIntermediateAddress* address = new (arena) HIntermediateAddress(array, offset, kNoDexPc); |
Alexandre Rames | 91a6516 | 2016-09-19 13:54:30 +0100 | [diff] [blame] | 259 | // TODO: Is it ok to not have this on the intermediate address? |
| 260 | // address->SetReferenceTypeInfo(array->GetReferenceTypeInfo()); |
Artem Serov | 328429f | 2016-07-06 16:23:04 +0100 | [diff] [blame] | 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 | |
| 281 | |
Artem Udovichenko | 4a0dad6 | 2016-01-26 12:28:31 +0300 | [diff] [blame] | 282 | } // namespace art |