diff options
-rw-r--r-- | compiler/optimizing/boolean_simplifier.cc | 4 | ||||
-rw-r--r-- | compiler/optimizing/code_generator_arm.cc | 24 | ||||
-rw-r--r-- | compiler/optimizing/code_generator_arm64.cc | 14 | ||||
-rw-r--r-- | compiler/optimizing/code_generator_x86.cc | 26 | ||||
-rw-r--r-- | compiler/optimizing/code_generator_x86_64.cc | 24 | ||||
-rw-r--r-- | compiler/optimizing/instruction_simplifier.cc | 11 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 11 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 6 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator.cc | 29 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator.h | 8 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator_test.cc | 4 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 11 | ||||
-rw-r--r-- | test/474-checker-boolean-input/src/Main.java | 45 |
13 files changed, 137 insertions, 80 deletions
diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc index 06328f249..6ebfb4507 100644 --- a/compiler/optimizing/boolean_simplifier.cc +++ b/compiler/optimizing/boolean_simplifier.cc @@ -72,8 +72,8 @@ static HInstruction* GetOppositeCondition(HInstruction* cond) { return graph->GetIntConstant(0); } } else { - // General case when 'cond' is another instruction of type boolean. - DCHECK_EQ(cond->GetType(), Primitive::Type::kPrimBoolean); + // General case when 'cond' is another instruction of type boolean, + // as verified by SSAChecker. return new (allocator) HBooleanNot(cond); } } diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 38fa04315..ae1fb537b 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -3898,9 +3898,11 @@ void InstructionCodeGeneratorARM::VisitInstanceOf(HInstanceOf* instruction) { SlowPathCodeARM* slow_path = nullptr; // Return 0 if `obj` is null. - // TODO: avoid this check if we know obj is not null. - __ cmp(obj, ShifterOperand(0)); - __ b(&zero, EQ); + // avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ cmp(obj, ShifterOperand(0)); + __ b(&zero, EQ); + } // Compare the class of `obj` with `cls`. __ LoadFromOffset(kLoadWord, out, obj, class_offset); __ cmp(out, ShifterOperand(cls)); @@ -3919,8 +3921,12 @@ void InstructionCodeGeneratorARM::VisitInstanceOf(HInstanceOf* instruction) { __ LoadImmediate(out, 1); __ b(&done); } - __ Bind(&zero); - __ LoadImmediate(out, 0); + + if (instruction->MustDoNullCheck() || instruction->IsClassFinal()) { + __ Bind(&zero); + __ LoadImmediate(out, 0); + } + if (slow_path != nullptr) { __ Bind(slow_path->GetExitLabel()); } @@ -3946,9 +3952,11 @@ void InstructionCodeGeneratorARM::VisitCheckCast(HCheckCast* instruction) { instruction, locations->InAt(1), locations->GetTemp(0), instruction->GetDexPc()); codegen_->AddSlowPath(slow_path); - // TODO: avoid this check if we know obj is not null. - __ cmp(obj, ShifterOperand(0)); - __ b(slow_path->GetExitLabel(), EQ); + // avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ cmp(obj, ShifterOperand(0)); + __ b(slow_path->GetExitLabel(), EQ); + } // Compare the class of `obj` with `cls`. __ LoadFromOffset(kLoadWord, temp, obj, class_offset); __ cmp(temp, ShifterOperand(cls)); diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 23ba339a9..1c6debdde 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -1452,8 +1452,10 @@ void InstructionCodeGeneratorARM64::VisitCheckCast(HCheckCast* instruction) { instruction, locations->InAt(1), LocationFrom(obj_cls), instruction->GetDexPc()); codegen_->AddSlowPath(slow_path); - // TODO: avoid this check if we know obj is not null. - __ Cbz(obj, slow_path->GetExitLabel()); + // Avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ Cbz(obj, slow_path->GetExitLabel()); + } // Compare the class of `obj` with `cls`. __ Ldr(obj_cls, HeapOperand(obj, mirror::Object::ClassOffset())); __ Cmp(obj_cls, cls); @@ -1855,9 +1857,11 @@ void InstructionCodeGeneratorARM64::VisitInstanceOf(HInstanceOf* instruction) { vixl::Label done; // Return 0 if `obj` is null. - // TODO: Avoid this check if we know `obj` is not null. - __ Mov(out, 0); - __ Cbz(obj, &done); + // Avoid null check if we know `obj` is not null. + if (instruction->MustDoNullCheck()) { + __ Mov(out, 0); + __ Cbz(obj, &done); + } // Compare the class of `obj` with `cls`. __ Ldr(out, HeapOperand(obj, mirror::Object::ClassOffset())); diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 3dcfca6a0..c604842d8 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -4250,9 +4250,11 @@ void InstructionCodeGeneratorX86::VisitInstanceOf(HInstanceOf* instruction) { SlowPathCodeX86* slow_path = nullptr; // Return 0 if `obj` is null. - // TODO: avoid this check if we know obj is not null. - __ testl(obj, obj); - __ j(kEqual, &zero); + // Avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ testl(obj, obj); + __ j(kEqual, &zero); + } __ movl(out, Address(obj, class_offset)); // Compare the class of `obj` with `cls`. if (cls.IsRegister()) { @@ -4277,8 +4279,12 @@ void InstructionCodeGeneratorX86::VisitInstanceOf(HInstanceOf* instruction) { __ movl(out, Immediate(1)); __ jmp(&done); } - __ Bind(&zero); - __ movl(out, Immediate(0)); + + if (instruction->MustDoNullCheck() || instruction->IsClassFinal()) { + __ Bind(&zero); + __ movl(out, Immediate(0)); + } + if (slow_path != nullptr) { __ Bind(slow_path->GetExitLabel()); } @@ -4303,11 +4309,13 @@ void InstructionCodeGeneratorX86::VisitCheckCast(HCheckCast* instruction) { instruction, locations->InAt(1), locations->GetTemp(0), instruction->GetDexPc()); codegen_->AddSlowPath(slow_path); - // TODO: avoid this check if we know obj is not null. - __ testl(obj, obj); - __ j(kEqual, slow_path->GetExitLabel()); - __ movl(temp, Address(obj, class_offset)); + // Avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ testl(obj, obj); + __ j(kEqual, slow_path->GetExitLabel()); + } + __ movl(temp, Address(obj, class_offset)); // Compare the class of `obj` with `cls`. if (cls.IsRegister()) { __ cmpl(temp, cls.AsRegister<Register>()); diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index b404f8de3..47425fb9a 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -4181,9 +4181,11 @@ void InstructionCodeGeneratorX86_64::VisitInstanceOf(HInstanceOf* instruction) { SlowPathCodeX86_64* slow_path = nullptr; // Return 0 if `obj` is null. - // TODO: avoid this check if we know obj is not null. - __ testl(obj, obj); - __ j(kEqual, &zero); + // Avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ testl(obj, obj); + __ j(kEqual, &zero); + } // Compare the class of `obj` with `cls`. __ movl(out, Address(obj, class_offset)); if (cls.IsRegister()) { @@ -4207,8 +4209,12 @@ void InstructionCodeGeneratorX86_64::VisitInstanceOf(HInstanceOf* instruction) { __ movl(out, Immediate(1)); __ jmp(&done); } - __ Bind(&zero); - __ movl(out, Immediate(0)); + + if (instruction->MustDoNullCheck() || instruction->IsClassFinal()) { + __ Bind(&zero); + __ movl(out, Immediate(0)); + } + if (slow_path != nullptr) { __ Bind(slow_path->GetExitLabel()); } @@ -4233,9 +4239,11 @@ void InstructionCodeGeneratorX86_64::VisitCheckCast(HCheckCast* instruction) { instruction, locations->InAt(1), locations->GetTemp(0), instruction->GetDexPc()); codegen_->AddSlowPath(slow_path); - // TODO: avoid this check if we know obj is not null. - __ testl(obj, obj); - __ j(kEqual, slow_path->GetExitLabel()); + // Avoid null check if we know obj is not null. + if (instruction->MustDoNullCheck()) { + __ testl(obj, obj); + __ j(kEqual, slow_path->GetExitLabel()); + } // Compare the class of `obj` with `cls`. __ movl(temp, Address(obj, class_offset)); if (cls.IsRegister()) { diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 225af77a1..2df7c166d 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -62,6 +62,7 @@ class InstructionSimplifierVisitor : public HGraphVisitor { void VisitSub(HSub* instruction) OVERRIDE; void VisitUShr(HUShr* instruction) OVERRIDE; void VisitXor(HXor* instruction) OVERRIDE; + void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; OptimizingCompilerStats* stats_; bool simplification_occurred_ = false; @@ -159,6 +160,10 @@ void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); + if (!check_cast->InputAt(0)->CanBeNull()) { + check_cast->ClearMustDoNullCheck(); + } + if (!load_class->IsResolved()) { // If the class couldn't be resolve it's not safe to compare against it. It's // default type would be Top which might be wider that the actual class type @@ -176,6 +181,12 @@ void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { } } +void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { + if (!instruction->InputAt(0)->CanBeNull()) { + instruction->ClearMustDoNullCheck(); + } +} + void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { HBasicBlock* block = check->GetBlock(); // Currently always keep the suspend check at entry. diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 19227cad6..b89487f4f 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -3355,6 +3355,7 @@ class HInstanceOf : public HExpression<2> { uint32_t dex_pc) : HExpression(Primitive::kPrimBoolean, SideEffects::None()), class_is_final_(class_is_final), + must_do_null_check_(true), dex_pc_(dex_pc) { SetRawInputAt(0, object); SetRawInputAt(1, constant); @@ -3374,10 +3375,15 @@ class HInstanceOf : public HExpression<2> { bool IsClassFinal() const { return class_is_final_; } + // Used only in code generation. + bool MustDoNullCheck() const { return must_do_null_check_; } + void ClearMustDoNullCheck() { must_do_null_check_ = false; } + DECLARE_INSTRUCTION(InstanceOf); private: const bool class_is_final_; + bool must_do_null_check_; const uint32_t dex_pc_; DISALLOW_COPY_AND_ASSIGN(HInstanceOf); @@ -3418,6 +3424,7 @@ class HCheckCast : public HTemplateInstruction<2> { uint32_t dex_pc) : HTemplateInstruction(SideEffects::None()), class_is_final_(class_is_final), + must_do_null_check_(true), dex_pc_(dex_pc) { SetRawInputAt(0, object); SetRawInputAt(1, constant); @@ -3436,6 +3443,9 @@ class HCheckCast : public HTemplateInstruction<2> { bool CanThrow() const OVERRIDE { return true; } + bool MustDoNullCheck() const { return must_do_null_check_; } + void ClearMustDoNullCheck() { must_do_null_check_ = false; } + uint32_t GetDexPc() const { return dex_pc_; } bool IsClassFinal() const { return class_is_final_; } @@ -3444,6 +3454,7 @@ class HCheckCast : public HTemplateInstruction<2> { private: const bool class_is_final_; + bool must_do_null_check_; const uint32_t dex_pc_; DISALLOW_COPY_AND_ASSIGN(HCheckCast); diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 218894fe0..d99d35998 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -324,7 +324,7 @@ static void RunOptimizations(HGraph* graph, HDeadCodeElimination dce2(graph, stats, "dead_code_elimination_final"); HConstantFolding fold1(graph); InstructionSimplifier simplify1(graph, stats); - HBooleanSimplifier boolean_not(graph); + HBooleanSimplifier boolean_simplify(graph); HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, stats); @@ -343,10 +343,10 @@ static void RunOptimizations(HGraph* graph, &dce1, &fold1, &simplify1, + &inliner, // BooleanSimplifier depends on the InstructionSimplifier removing redundant // suspend checks to recognize empty blocks. - &boolean_not, - &inliner, + &boolean_simplify, &fold2, &side_effects, &gvn, diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index f8e00f687..0fdf05195 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -378,7 +378,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { // Split just before first register use. size_t first_register_use = current->FirstRegisterUse(); if (first_register_use != kNoLifetime) { - LiveInterval* split = Split(current, first_register_use - 1); + LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); // Don't add directly to `unhandled`, it needs to be sorted and the start // of this new interval might be after intervals already in the list. AddSorted(&unhandled, split); @@ -997,7 +997,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { // If the first use of that instruction is after the last use of the found // register, we split this interval just before its first register use. AllocateSpillSlotFor(current); - LiveInterval* split = Split(current, first_register_use - 1); + LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); if (current == split) { DumpInterval(std::cerr, current); DumpAllIntervals(std::cerr); @@ -1100,6 +1100,31 @@ void RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInter } } +LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { + HBasicBlock* block_from = liveness_.GetBlockFromPosition(from); + HBasicBlock* block_to = liveness_.GetBlockFromPosition(to); + DCHECK(block_from != nullptr); + DCHECK(block_to != nullptr); + + // Both locations are in the same block. We split at the given location. + if (block_from == block_to) { + return Split(interval, to); + } + + // If `to` is in a loop, find the outermost loop header which does not contain `from`. + for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { + HBasicBlock* header = it.Current()->GetHeader(); + if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { + break; + } + block_to = header; + } + + // Split at the start of the found block, to piggy back on existing moves + // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). + return Split(interval, block_to->GetLifetimeStart()); +} + LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { DCHECK_GE(position, interval->GetStart()); DCHECK(!interval->IsDeadAt(position)); diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h index 717be7553..dc9c708ee 100644 --- a/compiler/optimizing/register_allocator.h +++ b/compiler/optimizing/register_allocator.h @@ -86,8 +86,12 @@ class RegisterAllocator { // Add `interval` in the given sorted list. static void AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval); - // Split `interval` at the position `at`. The new interval starts at `at`. - LiveInterval* Split(LiveInterval* interval, size_t at); + // Split `interval` at the position `position`. The new interval starts at `position`. + LiveInterval* Split(LiveInterval* interval, size_t position); + + // Split `interval` at a position between `from` and `to`. The method will try + // to find an optimal split position. + LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to); // Returns whether `reg` is blocked by the code generator. bool IsBlocked(int reg) const; diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index 182cd0e83..8c6d904a4 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -854,6 +854,10 @@ TEST(RegisterAllocatorTest, SpillInactive) { X86InstructionSetFeatures::FromCppDefines()); x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); SsaLivenessAnalysis liveness(graph, &codegen); + // Populate the instructions in the liveness object, to please the register allocator. + for (size_t i = 0; i < 32; ++i) { + liveness.instructions_from_lifetime_position_.Add(user); + } RegisterAllocator register_allocator(&allocator, &codegen, liveness); register_allocator.unhandled_core_intervals_.Add(fourth); diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index fe70d3a86..97254edb5 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -998,6 +998,15 @@ class SsaLivenessAnalysis : public ValueObject { return instructions_from_lifetime_position_.Get(index); } + HBasicBlock* GetBlockFromPosition(size_t index) const { + HInstruction* instruction = GetInstructionFromPosition(index / 2); + if (instruction == nullptr) { + // If we are at a block boundary, get the block following. + instruction = GetInstructionFromPosition((index / 2) + 1); + } + return instruction->GetBlock(); + } + HInstruction* GetTempUser(LiveInterval* temp) const { // A temporary shares the same lifetime start as the instruction that requires it. DCHECK(temp->IsTemp()); @@ -1068,6 +1077,8 @@ class SsaLivenessAnalysis : public ValueObject { GrowableArray<HInstruction*> instructions_from_lifetime_position_; size_t number_of_ssa_values_; + ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); + DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); }; diff --git a/test/474-checker-boolean-input/src/Main.java b/test/474-checker-boolean-input/src/Main.java index 1ebe14ede..9151986ca 100644 --- a/test/474-checker-boolean-input/src/Main.java +++ b/test/474-checker-boolean-input/src/Main.java @@ -23,35 +23,11 @@ public class Main { } /* - * Test that zero/one constants are accepted as Boolean inputs. - */ - - // CHECK-START: boolean Main.TestConstAsBoolean() inliner (before) - // CHECK-DAG: [[Invoke:z\d+]] InvokeStaticOrDirect - // CHECK-DAG: BooleanNot [ [[Invoke]] ] - - // CHECK-START: boolean Main.TestConstAsBoolean() inliner (after) - // CHECK-DAG: [[Const:i\d+]] IntConstant 1 - // CHECK-DAG: BooleanNot [ [[Const]] ] - - public static boolean InlineConst() { - return true; - } - - public static boolean TestConstAsBoolean() { - return InlineConst() != true ? true : false; - } - - /* * Test that integer Phis are accepted as Boolean inputs until * we implement a suitable type analysis. */ - // CHECK-START: boolean Main.TestPhiAsBoolean(int) inliner (before) - // CHECK-DAG: [[Invoke:z\d+]] InvokeStaticOrDirect - // CHECK-DAG: BooleanNot [ [[Invoke]] ] - - // CHECK-START: boolean Main.TestPhiAsBoolean(int) inliner (after) + // CHECK-START: boolean Main.TestPhiAsBoolean(int) boolean_simplifier (after) // CHECK-DAG: [[Phi:i\d+]] Phi // CHECK-DAG: BooleanNot [ [[Phi]] ] @@ -71,11 +47,7 @@ public class Main { * we implement a suitable type analysis. */ - // CHECK-START: boolean Main.TestAndAsBoolean(boolean, boolean) inliner (before) - // CHECK-DAG: [[Invoke:z\d+]] InvokeStaticOrDirect - // CHECK-DAG: BooleanNot [ [[Invoke]] ] - - // CHECK-START: boolean Main.TestAndAsBoolean(boolean, boolean) inliner (after) + // CHECK-START: boolean Main.TestAndAsBoolean(boolean, boolean) boolean_simplifier (after) // CHECK-DAG: [[And:i\d+]] And // CHECK-DAG: BooleanNot [ [[And]] ] @@ -92,11 +64,7 @@ public class Main { * we implement a suitable type analysis. */ - // CHECK-START: boolean Main.TestOrAsBoolean(boolean, boolean) inliner (before) - // CHECK-DAG: [[Invoke:z\d+]] InvokeStaticOrDirect - // CHECK-DAG: BooleanNot [ [[Invoke]] ] - - // CHECK-START: boolean Main.TestOrAsBoolean(boolean, boolean) inliner (after) + // CHECK-START: boolean Main.TestOrAsBoolean(boolean, boolean) boolean_simplifier (after) // CHECK-DAG: [[Or:i\d+]] Or // CHECK-DAG: BooleanNot [ [[Or]] ] @@ -113,11 +81,7 @@ public class Main { * we implement a suitable type analysis. */ - // CHECK-START: boolean Main.TestXorAsBoolean(boolean, boolean) inliner (before) - // CHECK-DAG: [[Invoke:z\d+]] InvokeStaticOrDirect - // CHECK-DAG: BooleanNot [ [[Invoke]] ] - - // CHECK-START: boolean Main.TestXorAsBoolean(boolean, boolean) inliner (after) + // CHECK-START: boolean Main.TestXorAsBoolean(boolean, boolean) boolean_simplifier (after) // CHECK-DAG: [[Xor:i\d+]] Xor // CHECK-DAG: BooleanNot [ [[Xor]] ] @@ -132,7 +96,6 @@ public class Main { public static void main(String[] args) { f1 = true; f2 = false; - assertBoolEquals(false, TestConstAsBoolean()); assertBoolEquals(true, TestPhiAsBoolean(0)); assertBoolEquals(false, TestPhiAsBoolean(42)); assertBoolEquals(true, TestAndAsBoolean(true, false)); |