From 1de1e11ac90db9fad8916ac43d43714ccb8d978f Mon Sep 17 00:00:00 2001 From: Artem Serov Date: Thu, 20 Jul 2017 16:33:59 +0100 Subject: ART: Try to statically evaluate some conditions. If a condition 'cond' is evaluated in an HIf instruction then in the successors of the this HIF_BLOCK we statically know the value of the condition (TRUE in TRUE_SUCC, FALSE in FALSE_SUCC). Using that we could replace another evaluation (use) EVAL of the same 'cond' with TRUE value (FALSE value) if every path from the ENTRY_BLOCK to EVAL_BLOCK contains the edge HIF_BLOCK->TRUE_SUCC (HIF_BLOCK->FALSE_SUCC). if (cond) { ... if (cond) { ... } ... int a = cond ? 5 : 105; ... } The patch is a prerequisite step for "Loop peeling to eliminate invariant exits" however it brings some value on its own with a tiny code size reduction in boot-framework.oat (-8Kb). Test: 458-checker-instruct-simplification Test: test-art-target, test-art-host. Change-Id: Ifbe45097dc2b5f098176fa1a1d023ea90b76d396 --- compiler/optimizing/instruction_simplifier.cc | 21 +++++++++++++++++++++ compiler/optimizing/nodes.cc | 14 ++++++++++---- compiler/optimizing/nodes.h | 16 +++++++++++++--- 3 files changed, 44 insertions(+), 7 deletions(-) (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 4c18e16c48..4c98d8323d 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -994,6 +994,27 @@ void InstructionSimplifierVisitor::VisitIf(HIf* instruction) { instruction->GetBlock()->SwapSuccessors(); RecordSimplification(); } + HInstruction* input = instruction->InputAt(0); + + // If a condition 'cond' is evaluated in an HIf instruction then in the successors of the + // IF_BLOCK we statically know the value of the condition (TRUE in TRUE_SUCC, FALSE in + // FALSE_SUCC). Using that we can replace another evaluation (use) EVAL of the same 'cond' + // with TRUE value (FALSE value) if every path from the ENTRY_BLOCK to EVAL_BLOCK contains the + // edge HIF_BLOCK->TRUE_SUCC (HIF_BLOCK->FALSE_SUCC). + if (!input->IsConstant()) { + HBasicBlock* true_succ = instruction->IfTrueSuccessor(); + HBasicBlock* false_succ = instruction->IfFalseSuccessor(); + + DCHECK_EQ(true_succ->GetPredecessors().size(), 1u); + input->ReplaceUsesDominatedBy( + true_succ->GetFirstInstruction(), GetGraph()->GetIntConstant(1), /* strictly */ false); + RecordSimplification(); + + DCHECK_EQ(false_succ->GetPredecessors().size(), 1u); + input->ReplaceUsesDominatedBy( + false_succ->GetFirstInstruction(), GetGraph()->GetIntConstant(0), /* strictly */ false); + RecordSimplification(); + } } void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index fa580d9bed..dda0243d3d 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1110,10 +1110,10 @@ bool HInstructionList::FoundBefore(const HInstruction* instruction1, return true; } -bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { +bool HInstruction::Dominates(HInstruction* other_instruction, bool strictly) const { if (other_instruction == this) { // An instruction does not strictly dominate itself. - return false; + return !strictly; } HBasicBlock* block = GetBlock(); HBasicBlock* other_block = other_instruction->GetBlock(); @@ -1147,6 +1147,10 @@ bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { } } +bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { + return Dominates(other_instruction, /* strictly */ true); +} + void HInstruction::RemoveEnvironment() { RemoveEnvironmentUses(this); environment_ = nullptr; @@ -1169,14 +1173,16 @@ void HInstruction::ReplaceWith(HInstruction* other) { DCHECK(env_uses_.empty()); } -void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) { +void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, + HInstruction* replacement, + bool strictly) { const HUseList& uses = GetUses(); for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { HInstruction* user = it->GetUser(); size_t index = it->GetIndex(); // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). ++it; - if (dominator->StrictlyDominates(user)) { + if (dominator->Dominates(user, strictly)) { user->ReplaceInput(replacement, index); } } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 66d5bfea32..07ab325a0e 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -2098,9 +2098,13 @@ class HInstruction : public ArenaObject { return IsRemovable() && !HasUses(); } - // Does this instruction strictly dominate `other_instruction`? - // Returns false if this instruction and `other_instruction` are the same. + // Does this instruction dominate (strictly or in regular sense depending on 'strictly') + // `other_instruction`? + // Returns '!strictly' if this instruction and `other_instruction` are the same. // Aborts if this instruction and `other_instruction` are both phis. + bool Dominates(HInstruction* other_instruction, bool strictly) const; + + // Return 'Dominates(other_instruction, /*strictly*/ true)'. bool StrictlyDominates(HInstruction* other_instruction) const; int GetId() const { return id_; } @@ -2161,7 +2165,13 @@ class HInstruction : public ArenaObject { void SetLocations(LocationSummary* locations) { locations_ = locations; } void ReplaceWith(HInstruction* instruction); - void ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement); + + // Replace all uses of the instruction which are dominated by 'dominator' with 'replacement'. + // 'strictly' determines whether strict or regular domination relation should be checked. + void ReplaceUsesDominatedBy(HInstruction* dominator, + HInstruction* replacement, + bool strictly = true); + void ReplaceInput(HInstruction* replacement, size_t index); // This is almost the same as doing `ReplaceWith()`. But in this helper, the -- cgit v1.2.3-59-g8ed1b