diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/image_writer.cc | 4 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 147 | ||||
| -rw-r--r-- | compiler/optimizing/instruction_simplifier.cc | 26 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 9 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 5 |
5 files changed, 149 insertions, 42 deletions
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc index 59f339a9a2..a37bf4b9fe 100644 --- a/compiler/image_writer.cc +++ b/compiler/image_writer.cc @@ -51,6 +51,7 @@ #include "lock_word.h" #include "mirror/array-inl.h" #include "mirror/class-inl.h" +#include "mirror/class_ext.h" #include "mirror/class_loader.h" #include "mirror/dex_cache.h" #include "mirror/dex_cache-inl.h" @@ -757,7 +758,8 @@ bool ImageWriter::PruneAppImageClassInternal( if (klass->GetStatus() == mirror::Class::kStatusError) { result = true; } else { - CHECK(klass->GetVerifyError() == nullptr) << klass->PrettyClass(); + ObjPtr<mirror::ClassExt> ext(klass->GetExtData()); + CHECK(ext.IsNull() || ext->GetVerifyError() == nullptr) << klass->PrettyClass(); } if (!result) { // Check interfaces since these wont be visited through VisitReferences.) diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 7cc8b1ea4c..235793d8d2 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -58,22 +58,90 @@ static bool IsIntAndGet(HInstruction* instruction, int64_t* value) { } /** - * An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as length + b - * because length >= 0 is true. This makes it more likely the bound is useful to clients. + * Detects an instruction that is >= 0. As long as the value is carried by + * a single instruction, arithmetic wrap-around cannot occur. */ -static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) { - int64_t value; - if (v.is_known && - v.a_constant >= 1 && - v.instruction->IsDiv() && - v.instruction->InputAt(0)->IsArrayLength() && - IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { - return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant); +static bool IsGEZero(HInstruction* instruction) { + DCHECK(instruction != nullptr); + if (instruction->IsArrayLength()) { + return true; + } else if (instruction->IsInvokeStaticOrDirect()) { + switch (instruction->AsInvoke()->GetIntrinsic()) { + case Intrinsics::kMathMinIntInt: + case Intrinsics::kMathMinLongLong: + // Instruction MIN(>=0, >=0) is >= 0. + return IsGEZero(instruction->InputAt(0)) && + IsGEZero(instruction->InputAt(1)); + case Intrinsics::kMathAbsInt: + case Intrinsics::kMathAbsLong: + // Instruction ABS(x) is >= 0. + return true; + default: + break; + } + } + int64_t value = -1; + return IsIntAndGet(instruction, &value) && value >= 0; +} + +/** Hunts "under the hood" for a suitable instruction at the hint. */ +static bool IsMaxAtHint( + HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) { + if (instruction->IsInvokeStaticOrDirect()) { + switch (instruction->AsInvoke()->GetIntrinsic()) { + case Intrinsics::kMathMinIntInt: + case Intrinsics::kMathMinLongLong: + // For MIN(x, y), return most suitable x or y as maximum. + return IsMaxAtHint(instruction->InputAt(0), hint, suitable) || + IsMaxAtHint(instruction->InputAt(1), hint, suitable); + default: + break; + } + } else { + *suitable = instruction; + while (instruction->IsArrayLength() || + instruction->IsNullCheck() || + instruction->IsNewArray()) { + instruction = instruction->InputAt(0); + } + return instruction == hint; + } + return false; +} + +/** Post-analysis simplification of a minimum value that makes the bound more useful to clients. */ +static InductionVarRange::Value SimplifyMin(InductionVarRange::Value v) { + if (v.is_known && v.a_constant == 1 && v.b_constant <= 0) { + // If a == 1, instruction >= 0 and b <= 0, just return the constant b. + // No arithmetic wrap-around can occur. + if (IsGEZero(v.instruction)) { + return InductionVarRange::Value(v.b_constant); + } } return v; } -/** Helper method to test for a constant value. */ +/** Post-analysis simplification of a maximum value that makes the bound more useful to clients. */ +static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v, HInstruction* hint) { + if (v.is_known && v.a_constant >= 1) { + // An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as + // length + b because length >= 0 is true. + int64_t value; + if (v.instruction->IsDiv() && + v.instruction->InputAt(0)->IsArrayLength() && + IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { + return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant); + } + // If a == 1, the most suitable one suffices as maximum value. + HInstruction* suitable = nullptr; + if (v.a_constant == 1 && IsMaxAtHint(v.instruction, hint, &suitable)) { + return InductionVarRange::Value(suitable, 1, v.b_constant); + } + } + return v; +} + +/** Tests for a constant value. */ static bool IsConstantValue(InductionVarRange::Value v) { return v.is_known && v.a_constant == 0; } @@ -97,7 +165,7 @@ static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primi } } -/** Helper method to insert an instruction. */ +/** Inserts an instruction. */ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { DCHECK(block != nullptr); DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId(); @@ -106,7 +174,7 @@ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { return instruction; } -/** Helper method to obtain loop's control instruction. */ +/** Obtains loop's control instruction. */ static HInstruction* GetLoopControl(HLoopInformation* loop) { DCHECK(loop != nullptr); return loop->GetHeader()->GetLastInstruction(); @@ -150,9 +218,14 @@ bool InductionVarRange::GetInductionRange(HInstruction* context, chase_hint_ = chase_hint; bool in_body = context->GetBlock() != loop->GetHeader(); int64_t stride_value = 0; - *min_val = GetVal(info, trip, in_body, /* is_min */ true); - *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false)); + *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); + *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false), chase_hint); *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip); + chase_hint_ = nullptr; + // Retry chasing constants for wrap-around (merge sensitive). + if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) { + *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); + } return true; } @@ -175,7 +248,7 @@ bool InductionVarRange::CanGenerateRange(HInstruction* context, needs_taken_test) && (stride_value == -1 || stride_value == 0 || - stride_value == 1); // avoid wrap-around anomalies. + stride_value == 1); // avoid arithmetic wrap-around anomalies. } void InductionVarRange::GenerateRange(HInstruction* context, @@ -302,7 +375,8 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, return true; } } - // Try range analysis on the invariant, but only on proper range to avoid wrap-around anomalies. + // Try range analysis on the invariant, only accept a proper range + // to avoid arithmetic wrap-around anomalies. Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true); Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false); if (IsConstantValue(min_val) && @@ -450,25 +524,26 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, bool in_body, bool is_min) const { - // Stop chasing the instruction at constant or hint. - int64_t value; - if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { - return Value(static_cast<int32_t>(value)); - } else if (instruction == chase_hint_) { - return Value(instruction, 1, 0); - } - // Special cases when encountering a single instruction that denotes trip count in the - // loop-body: min is 1 and, when chasing constants, max of safe trip-count is max int - if (in_body && trip != nullptr && instruction == trip->op_a->fetch) { + // Special case when chasing constants: single instruction that denotes trip count in the + // loop-body is minimal 1 and maximal, with safe trip-count, max int, + if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) { if (is_min) { return Value(1); - } else if (chase_hint_ == nullptr && !IsUnsafeTripCount(trip)) { + } else if (!IsUnsafeTripCount(trip)) { return Value(std::numeric_limits<int32_t>::max()); } } - // Chase the instruction a bit deeper into the HIR tree, so that it becomes more likely - // range analysis will compare the same instructions as terminal nodes. - if (instruction->IsAdd()) { + // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that + // it becomes more likely range analysis will compare the same instructions as terminal nodes. + int64_t value; + if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { + // Proper constant reveals best information. + return Value(static_cast<int32_t>(value)); + } else if (instruction == chase_hint_) { + // At hint, fetch is represented by itself. + return Value(instruction, 1, 0); + } else if (instruction->IsAdd()) { + // Incorporate suitable constants in the chased value. if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { return AddValue(Value(static_cast<int32_t>(value)), GetFetch(instruction->InputAt(1), trip, in_body, is_min)); @@ -477,14 +552,14 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, Value(static_cast<int32_t>(value))); } } else if (instruction->IsArrayLength()) { - // Return extreme values when chasing constants. Otherwise, chase deeper. + // Exploit length properties when chasing constants or chase into a new array declaration. if (chase_hint_ == nullptr) { return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max()); } else if (instruction->InputAt(0)->IsNewArray()) { return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); } } else if (instruction->IsTypeConversion()) { - // Since analysis is 32-bit (or narrower) we allow a widening along the path. + // Since analysis is 32-bit (or narrower), chase beyond widening along the path. if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { return GetFetch(instruction->InputAt(0), trip, in_body, is_min); @@ -506,6 +581,7 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, !IsUnsafeTripCount(next_trip)) { return GetVal(next_info, next_trip, next_in_body, is_min); } + // Fetch is represented by itself. return Value(instruction, 1, 0); } @@ -870,10 +946,11 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, HInstruction* opb = nullptr; switch (info->induction_class) { case HInductionVarAnalysis::kInvariant: - // Invariants. + // Invariants (note that even though is_min does not impact code generation for + // invariants, some effort is made to keep this parameter consistent). switch (info->operation) { case HInductionVarAnalysis::kAdd: - case HInductionVarAnalysis::kXor: + case HInductionVarAnalysis::kXor: // no proper is_min for second arg case HInductionVarAnalysis::kLT: case HInductionVarAnalysis::kLE: case HInductionVarAnalysis::kGT: diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index e4d280f26d..e06fdee370 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -111,9 +111,11 @@ class InstructionSimplifierVisitor : public HGraphDelegateVisitor { OptimizingCompilerStats* stats_; bool simplification_occurred_ = false; int simplifications_at_current_position_ = 0; - // We ensure we do not loop infinitely. The value is a finger in the air guess - // that should allow enough simplification. - static constexpr int kMaxSamePositionSimplifications = 10; + // We ensure we do not loop infinitely. The value should not be too high, since that + // would allow looping around the same basic block too many times. The value should + // not be too low either, however, since we want to allow revisiting a basic block + // with many statements and simplifications at least once. + static constexpr int kMaxSamePositionSimplifications = 50; }; void InstructionSimplifier::Run() { @@ -605,11 +607,23 @@ static HCondition* GetOppositeConditionSwapOps(ArenaAllocator* arena, HInstructi return nullptr; } +static bool CmpHasBoolType(HInstruction* input, HInstruction* cmp) { + if (input->GetType() == Primitive::kPrimBoolean) { + return true; // input has direct boolean type + } else if (cmp->GetUses().HasExactlyOneElement()) { + // Comparison also has boolean type if both its input and the instruction + // itself feed into the same phi node. + HInstruction* user = cmp->GetUses().front().GetUser(); + return user->IsPhi() && user->HasInput(input) && user->HasInput(cmp); + } + return false; +} + void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { HInstruction* input_const = equal->GetConstantRight(); if (input_const != nullptr) { HInstruction* input_value = equal->GetLeastConstantLeft(); - if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { + if (CmpHasBoolType(input_value, equal) && input_const->IsIntConstant()) { HBasicBlock* block = equal->GetBlock(); // We are comparing the boolean to a constant which is of type int and can // be any constant. @@ -619,6 +633,7 @@ void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { block->RemoveInstruction(equal); RecordSimplification(); } else if (input_const->AsIntConstant()->IsFalse()) { + // Replace (bool_value == false) with !bool_value equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, equal)); block->RemoveInstruction(equal); RecordSimplification(); @@ -640,11 +655,12 @@ void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { HInstruction* input_const = not_equal->GetConstantRight(); if (input_const != nullptr) { HInstruction* input_value = not_equal->GetLeastConstantLeft(); - if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { + if (CmpHasBoolType(input_value, not_equal) && input_const->IsIntConstant()) { HBasicBlock* block = not_equal->GetBlock(); // We are comparing the boolean to a constant which is of type int and can // be any constant. if (input_const->AsIntConstant()->IsTrue()) { + // Replace (bool_value != true) with !bool_value not_equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, not_equal)); block->RemoveInstruction(not_equal); RecordSimplification(); diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 6a45149509..ce2edde1c1 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1855,6 +1855,15 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { size_t InputCount() const { return GetInputRecords().size(); } HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } + bool HasInput(HInstruction* input) const { + for (const HInstruction* i : GetInputs()) { + if (i == input) { + return true; + } + } + return false; + } + void SetRawInputAt(size_t index, HInstruction* input) { SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); } diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 19fd6f95c3..a4847601f5 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -755,6 +755,8 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, HDeadCodeElimination* dce1 = new (arena) HDeadCodeElimination( graph, stats, "dead_code_elimination$initial"); HDeadCodeElimination* dce2 = new (arena) HDeadCodeElimination( + graph, stats, "dead_code_elimination$after_inlining"); + HDeadCodeElimination* dce3 = new (arena) HDeadCodeElimination( graph, stats, "dead_code_elimination$final"); HConstantFolding* fold1 = new (arena) HConstantFolding(graph); InstructionSimplifier* simplify1 = new (arena) InstructionSimplifier(graph, stats); @@ -795,6 +797,7 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, select_generator, fold2, // TODO: if we don't inline we can also skip fold2. simplify2, + dce2, side_effects, gvn, licm, @@ -804,7 +807,7 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, fold3, // evaluates code generated by dynamic bce simplify3, lse, - dce2, + dce3, // The codegen has a few assumptions that only the instruction simplifier // can satisfy. For example, the code generator does not expect to see a // HTypeConversion from a type to the same type. |