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