instruction_simplifier.cc revision b2fd7bca70b580921eebf7c45769c39d2dfd8a5a
1/* 2 * Copyright (C) 2014 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.h" 18 19#include "mirror/class-inl.h" 20#include "scoped_thread_state_change.h" 21 22namespace art { 23 24class InstructionSimplifierVisitor : public HGraphVisitor { 25 public: 26 InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats) 27 : HGraphVisitor(graph), stats_(stats) {} 28 29 private: 30 void VisitShift(HBinaryOperation* shift); 31 32 void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE; 33 void VisitEqual(HEqual* equal) OVERRIDE; 34 void VisitArraySet(HArraySet* equal) OVERRIDE; 35 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 36 void VisitNullCheck(HNullCheck* instruction) OVERRIDE; 37 void VisitArrayLength(HArrayLength* instruction) OVERRIDE; 38 void VisitCheckCast(HCheckCast* instruction) OVERRIDE; 39 void VisitAdd(HAdd* instruction) OVERRIDE; 40 void VisitAnd(HAnd* instruction) OVERRIDE; 41 void VisitDiv(HDiv* instruction) OVERRIDE; 42 void VisitMul(HMul* instruction) OVERRIDE; 43 void VisitOr(HOr* instruction) OVERRIDE; 44 void VisitShl(HShl* instruction) OVERRIDE; 45 void VisitShr(HShr* instruction) OVERRIDE; 46 void VisitSub(HSub* instruction) OVERRIDE; 47 void VisitUShr(HUShr* instruction) OVERRIDE; 48 void VisitXor(HXor* instruction) OVERRIDE; 49 50 OptimizingCompilerStats* stats_; 51}; 52 53void InstructionSimplifier::Run() { 54 InstructionSimplifierVisitor visitor(graph_, stats_); 55 visitor.VisitInsertionOrder(); 56} 57 58namespace { 59 60bool AreAllBitsSet(HConstant* constant) { 61 return Int64FromConstant(constant) == -1; 62} 63 64} // namespace 65 66void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 67 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 68 HConstant* input_cst = instruction->GetConstantRight(); 69 HInstruction* input_other = instruction->GetLeastConstantLeft(); 70 71 if ((input_cst != nullptr) && input_cst->IsZero()) { 72 // Replace code looking like 73 // SHL dst, src, 0 74 // with 75 // src 76 instruction->ReplaceWith(input_other); 77 instruction->GetBlock()->RemoveInstruction(instruction); 78 } 79} 80 81void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 82 HInstruction* obj = null_check->InputAt(0); 83 if (!obj->CanBeNull()) { 84 null_check->ReplaceWith(obj); 85 null_check->GetBlock()->RemoveInstruction(null_check); 86 if (stats_ != nullptr) { 87 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 88 } 89 } 90} 91 92void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 93 HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); 94 if (!load_class->IsResolved()) { 95 // If the class couldn't be resolve it's not safe to compare against it. It's 96 // default type would be Top which might be wider that the actual class type 97 // and thus producing wrong results. 98 return; 99 } 100 ReferenceTypeInfo obj_rti = check_cast->InputAt(0)->GetReferenceTypeInfo(); 101 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); 102 ScopedObjectAccess soa(Thread::Current()); 103 if (class_rti.IsSupertypeOf(obj_rti)) { 104 check_cast->GetBlock()->RemoveInstruction(check_cast); 105 if (stats_ != nullptr) { 106 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 107 } 108 } 109} 110 111void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { 112 HBasicBlock* block = check->GetBlock(); 113 // Currently always keep the suspend check at entry. 114 if (block->IsEntryBlock()) return; 115 116 // Currently always keep suspend checks at loop entry. 117 if (block->IsLoopHeader() && block->GetFirstInstruction() == check) { 118 DCHECK(block->GetLoopInformation()->GetSuspendCheck() == check); 119 return; 120 } 121 122 // Remove the suspend check that was added at build time for the baseline 123 // compiler. 124 block->RemoveInstruction(check); 125} 126 127void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 128 HInstruction* input1 = equal->InputAt(0); 129 HInstruction* input2 = equal->InputAt(1); 130 if (input1->GetType() == Primitive::kPrimBoolean && input2->IsIntConstant()) { 131 if (input2->AsIntConstant()->GetValue() == 1) { 132 // Replace (bool_value == 1) with bool_value 133 equal->ReplaceWith(equal->InputAt(0)); 134 equal->GetBlock()->RemoveInstruction(equal); 135 } else { 136 // We should replace (bool_value == 0) with !bool_value, but we unfortunately 137 // do not have such instruction. 138 DCHECK_EQ(input2->AsIntConstant()->GetValue(), 0); 139 } 140 } 141} 142 143void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 144 HInstruction* input = instruction->InputAt(0); 145 // If the array is a NewArray with constant size, replace the array length 146 // with the constant instruction. This helps the bounds check elimination phase. 147 if (input->IsNewArray()) { 148 input = input->InputAt(0); 149 if (input->IsIntConstant()) { 150 instruction->ReplaceWith(input); 151 } 152 } 153} 154 155void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 156 HInstruction* value = instruction->GetValue(); 157 if (value->GetType() != Primitive::kPrimNot) return; 158 159 if (value->IsArrayGet()) { 160 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 161 // If the code is just swapping elements in the array, no need for a type check. 162 instruction->ClearNeedsTypeCheck(); 163 } 164 } 165} 166 167void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 168 if (instruction->GetResultType() == instruction->GetInputType()) { 169 // Remove the instruction if it's converting to the same type. 170 instruction->ReplaceWith(instruction->GetInput()); 171 instruction->GetBlock()->RemoveInstruction(instruction); 172 } 173} 174 175void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 176 HConstant* input_cst = instruction->GetConstantRight(); 177 HInstruction* input_other = instruction->GetLeastConstantLeft(); 178 if ((input_cst != nullptr) && input_cst->IsZero()) { 179 // Replace code looking like 180 // ADD dst, src, 0 181 // with 182 // src 183 instruction->ReplaceWith(input_other); 184 instruction->GetBlock()->RemoveInstruction(instruction); 185 } 186} 187 188void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 189 HConstant* input_cst = instruction->GetConstantRight(); 190 HInstruction* input_other = instruction->GetLeastConstantLeft(); 191 192 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 193 // Replace code looking like 194 // AND dst, src, 0xFFF...FF 195 // with 196 // src 197 instruction->ReplaceWith(input_other); 198 instruction->GetBlock()->RemoveInstruction(instruction); 199 return; 200 } 201 202 // We assume that GVN has run before, so we only perform a pointer comparison. 203 // If for some reason the values are equal but the pointers are different, we 204 // are still correct and only miss an optimisation opportunity. 205 if (instruction->GetLeft() == instruction->GetRight()) { 206 // Replace code looking like 207 // AND dst, src, src 208 // with 209 // src 210 instruction->ReplaceWith(instruction->GetLeft()); 211 instruction->GetBlock()->RemoveInstruction(instruction); 212 } 213} 214 215void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 216 HConstant* input_cst = instruction->GetConstantRight(); 217 HInstruction* input_other = instruction->GetLeastConstantLeft(); 218 Primitive::Type type = instruction->GetType(); 219 220 if ((input_cst != nullptr) && input_cst->IsOne()) { 221 // Replace code looking like 222 // DIV dst, src, 1 223 // with 224 // src 225 instruction->ReplaceWith(input_other); 226 instruction->GetBlock()->RemoveInstruction(instruction); 227 return; 228 } 229 230 if ((input_cst != nullptr) && input_cst->IsMinusOne() && 231 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 232 // Replace code looking like 233 // DIV dst, src, -1 234 // with 235 // NEG dst, src 236 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 237 instruction, (new (GetGraph()->GetArena()) HNeg(type, input_other))); 238 } 239} 240 241void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 242 HConstant* input_cst = instruction->GetConstantRight(); 243 HInstruction* input_other = instruction->GetLeastConstantLeft(); 244 Primitive::Type type = instruction->GetType(); 245 HBasicBlock* block = instruction->GetBlock(); 246 ArenaAllocator* allocator = GetGraph()->GetArena(); 247 248 if (input_cst == nullptr) { 249 return; 250 } 251 252 if (input_cst->IsOne()) { 253 // Replace code looking like 254 // MUL dst, src, 1 255 // with 256 // src 257 instruction->ReplaceWith(input_other); 258 instruction->GetBlock()->RemoveInstruction(instruction); 259 return; 260 } 261 262 if (input_cst->IsMinusOne() && 263 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 264 // Replace code looking like 265 // MUL dst, src, -1 266 // with 267 // NEG dst, src 268 HNeg* neg = new (allocator) HNeg(type, input_other); 269 block->ReplaceAndRemoveInstructionWith(instruction, neg); 270 return; 271 } 272 273 if (Primitive::IsFloatingPointType(type) && 274 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 275 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 276 // Replace code looking like 277 // FP_MUL dst, src, 2.0 278 // with 279 // FP_ADD dst, src, src 280 // The 'int' and 'long' cases are handled below. 281 block->ReplaceAndRemoveInstructionWith(instruction, 282 new (allocator) HAdd(type, input_other, input_other)); 283 return; 284 } 285 286 if (Primitive::IsIntOrLongType(type)) { 287 int64_t factor = Int64FromConstant(input_cst); 288 // We expect the `0` case to have been handled in the constant folding pass. 289 DCHECK_NE(factor, 0); 290 if (IsPowerOfTwo(factor)) { 291 // Replace code looking like 292 // MUL dst, src, pow_of_2 293 // with 294 // SHL dst, src, log2(pow_of_2) 295 HIntConstant* shift = new (allocator) HIntConstant(WhichPowerOf2(factor)); 296 block->InsertInstructionBefore(shift, instruction); 297 HShl* shl = new(allocator) HShl(type, input_other, shift); 298 block->ReplaceAndRemoveInstructionWith(instruction, shl); 299 } 300 } 301} 302 303void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 304 HConstant* input_cst = instruction->GetConstantRight(); 305 HInstruction* input_other = instruction->GetLeastConstantLeft(); 306 307 if ((input_cst != nullptr) && input_cst->IsZero()) { 308 // Replace code looking like 309 // OR dst, src, 0 310 // with 311 // src 312 instruction->ReplaceWith(input_other); 313 instruction->GetBlock()->RemoveInstruction(instruction); 314 return; 315 } 316 317 // We assume that GVN has run before, so we only perform a pointer comparison. 318 // If for some reason the values are equal but the pointers are different, we 319 // are still correct and only miss an optimisation opportunity. 320 if (instruction->GetLeft() == instruction->GetRight()) { 321 // Replace code looking like 322 // OR dst, src, src 323 // with 324 // src 325 instruction->ReplaceWith(instruction->GetLeft()); 326 instruction->GetBlock()->RemoveInstruction(instruction); 327 } 328} 329 330void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 331 VisitShift(instruction); 332} 333 334void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 335 VisitShift(instruction); 336} 337 338void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 339 HConstant* input_cst = instruction->GetConstantRight(); 340 HInstruction* input_other = instruction->GetLeastConstantLeft(); 341 342 if ((input_cst != nullptr) && input_cst->IsZero()) { 343 // Replace code looking like 344 // SUB dst, src, 0 345 // with 346 // src 347 instruction->ReplaceWith(input_other); 348 instruction->GetBlock()->RemoveInstruction(instruction); 349 return; 350 } 351 352 Primitive::Type type = instruction->GetType(); 353 if (!Primitive::IsIntegralType(type)) { 354 return; 355 } 356 357 HBasicBlock* block = instruction->GetBlock(); 358 ArenaAllocator* allocator = GetGraph()->GetArena(); 359 360 if (instruction->GetLeft()->IsConstant()) { 361 int64_t left = Int64FromConstant(instruction->GetLeft()->AsConstant()); 362 if (left == 0) { 363 // Replace code looking like 364 // SUB dst, 0, src 365 // with 366 // NEG dst, src 367 // Note that we cannot optimise `0.0 - x` to `-x` for floating-point. When 368 // `x` is `0.0`, the former expression yields `0.0`, while the later 369 // yields `-0.0`. 370 HNeg* neg = new (allocator) HNeg(type, instruction->GetRight()); 371 block->ReplaceAndRemoveInstructionWith(instruction, neg); 372 } 373 } 374} 375 376void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 377 VisitShift(instruction); 378} 379 380void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 381 HConstant* input_cst = instruction->GetConstantRight(); 382 HInstruction* input_other = instruction->GetLeastConstantLeft(); 383 384 if ((input_cst != nullptr) && input_cst->IsZero()) { 385 // Replace code looking like 386 // XOR dst, src, 0 387 // with 388 // src 389 instruction->ReplaceWith(input_other); 390 instruction->GetBlock()->RemoveInstruction(instruction); 391 return; 392 } 393 394 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 395 // Replace code looking like 396 // XOR dst, src, 0xFFF...FF 397 // with 398 // NOT dst, src 399 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 400 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 401 return; 402 } 403} 404 405} // namespace art 406