ART: Simplify HRem to reuse existing HDiv
A pattern seen in libcore and SPECjvm2008 workloads is a pair of HRem/HDiv
having the same dividend and divisor. The code generator processes
them separately and generates duplicated instructions calculating HDiv.
This CL adds detection of such a pattern to the instruction simplifier.
This optimization affects HInductionVarAnalysis and HLoopOptimization
preventing some loop optimizations. To avoid this the instruction simplifier
has the loop_friendly mode which means not to optimize HRems if they are in a loop.
A microbenchmark run on Pixel 3 shows the following improvements:
| little cores | big cores
arm32 Int32 | +21% | +40%
arm32 Int64 | +46% | +44%
arm64 Int32 | +27% | +14%
arm64 Int64 | +33% | +27%
Test: 411-checker-instruct-simplifier-hrem
Test: test.py --host --optimizing --jit --gtest --interpreter
Test: test.py --target --optimizing --jit --interpreter
Test: run-gtests.sh
Change-Id: I376a1bd299d7fe10acad46771236edd5f85dfe56
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 70cef49..4a618de 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3067,7 +3067,6 @@
Register quotient,
int64_t divisor,
UseScratchRegisterScope* temps_scope) {
- // TODO: Strength reduction for msub.
Register temp_imm = temps_scope->AcquireSameSizeAs(out);
__ Mov(temp_imm, divisor);
__ Msub(out, quotient, temp_imm, dividend);
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 5ac77a5..d586306 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -37,10 +37,12 @@
public:
InstructionSimplifierVisitor(HGraph* graph,
CodeGenerator* codegen,
- OptimizingCompilerStats* stats)
+ OptimizingCompilerStats* stats,
+ bool be_loop_friendly)
: HGraphDelegateVisitor(graph),
codegen_(codegen),
- stats_(stats) {}
+ stats_(stats),
+ be_loop_friendly_(be_loop_friendly) {}
bool Run();
@@ -65,6 +67,7 @@
bool TryHandleAssociativeAndCommutativeOperation(HBinaryOperation* instruction);
bool TrySubtractionChainSimplification(HBinaryOperation* instruction);
bool TryCombineVecMultiplyAccumulate(HVecMul* mul);
+ void TryToReuseDiv(HRem* rem);
void VisitShift(HBinaryOperation* shift);
void VisitEqual(HEqual* equal) override;
@@ -90,6 +93,7 @@
void VisitAbove(HAbove* condition) override;
void VisitAboveOrEqual(HAboveOrEqual* condition) override;
void VisitDiv(HDiv* instruction) override;
+ void VisitRem(HRem* instruction) override;
void VisitMul(HMul* instruction) override;
void VisitNeg(HNeg* instruction) override;
void VisitNot(HNot* instruction) override;
@@ -122,6 +126,13 @@
OptimizingCompilerStats* stats_;
bool simplification_occurred_ = false;
int simplifications_at_current_position_ = 0;
+ // Prohibit optimizations which can affect HInductionVarAnalysis/HLoopOptimization
+ // and prevent loop optimizations:
+ // true - avoid such optimizations.
+ // false - allow such optimizations.
+ // Checked by the following optimizations:
+ // - TryToReuseDiv: simplification of Div+Rem into Div+Mul+Sub.
+ bool be_loop_friendly_;
// 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
@@ -135,7 +146,9 @@
visitor.VisitReversePostOrder();
}
- InstructionSimplifierVisitor visitor(graph_, codegen_, stats_);
+ bool be_loop_friendly = (use_all_optimizations_ == false);
+
+ InstructionSimplifierVisitor visitor(graph_, codegen_, stats_, be_loop_friendly);
return visitor.Run();
}
@@ -1691,6 +1704,71 @@
}
}
+
+// Search HDiv having the specified dividend and divisor which is in the specified basic block.
+// Return nullptr if nothing has been found.
+static HInstruction* FindDivWithInputsInBasicBlock(HInstruction* dividend,
+ HInstruction* divisor,
+ HBasicBlock* basic_block) {
+ for (const HUseListNode<HInstruction*>& use : dividend->GetUses()) {
+ HInstruction* user = use.GetUser();
+ if (user->GetBlock() == basic_block && user->IsDiv() && user->InputAt(1) == divisor) {
+ return user;
+ }
+ }
+ return nullptr;
+}
+
+// If there is Div with the same inputs as Rem and in the same basic block, it can be reused.
+// Rem is replaced with Mul+Sub which use the found Div.
+void InstructionSimplifierVisitor::TryToReuseDiv(HRem* rem) {
+ // As the optimization replaces Rem with Mul+Sub they prevent some loop optimizations
+ // if the Rem is in a loop.
+ // Check if it is allowed to optimize such Rems.
+ if (rem->IsInLoop() && be_loop_friendly_) {
+ return;
+ }
+ DataType::Type type = rem->GetResultType();
+ if (!DataType::IsIntOrLongType(type)) {
+ return;
+ }
+
+ HBasicBlock* basic_block = rem->GetBlock();
+ HInstruction* dividend = rem->GetLeft();
+ HInstruction* divisor = rem->GetRight();
+
+ if (divisor->IsConstant()) {
+ HConstant* input_cst = rem->GetConstantRight();
+ DCHECK(input_cst->IsIntConstant() || input_cst->IsLongConstant());
+ int64_t cst_value = Int64FromConstant(input_cst);
+ if (cst_value == std::numeric_limits<int64_t>::min() || IsPowerOfTwo(std::abs(cst_value))) {
+ // Such cases are usually handled in the code generator because they don't need Div at all.
+ return;
+ }
+ }
+
+ HInstruction* quotient = FindDivWithInputsInBasicBlock(dividend, divisor, basic_block);
+ if (quotient == nullptr) {
+ return;
+ }
+ if (!quotient->StrictlyDominates(rem)) {
+ quotient->MoveBefore(rem);
+ }
+
+ ArenaAllocator* allocator = GetGraph()->GetAllocator();
+ HInstruction* mul = new (allocator) HMul(type, quotient, divisor);
+ basic_block->InsertInstructionBefore(mul, rem);
+ HInstruction* sub = new (allocator) HSub(type, dividend, mul);
+ basic_block->InsertInstructionBefore(sub, rem);
+ rem->ReplaceWith(sub);
+ basic_block->RemoveInstruction(rem);
+ RecordSimplification();
+}
+
+void InstructionSimplifierVisitor::VisitRem(HRem* rem) {
+ TryToReuseDiv(rem);
+}
+
void InstructionSimplifierVisitor::VisitMul(HMul* instruction) {
HConstant* input_cst = instruction->GetConstantRight();
HInstruction* input_other = instruction->GetLeastConstantLeft();
diff --git a/compiler/optimizing/instruction_simplifier.h b/compiler/optimizing/instruction_simplifier.h
index 982a24a..feea771 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -40,9 +40,11 @@
InstructionSimplifier(HGraph* graph,
CodeGenerator* codegen,
OptimizingCompilerStats* stats = nullptr,
- const char* name = kInstructionSimplifierPassName)
+ const char* name = kInstructionSimplifierPassName,
+ bool use_all_optimizations = false)
: HOptimization(graph, name, stats),
- codegen_(codegen) {}
+ codegen_(codegen),
+ use_all_optimizations_(use_all_optimizations) {}
static constexpr const char* kInstructionSimplifierPassName = "instruction_simplifier";
@@ -51,6 +53,9 @@
private:
CodeGenerator* codegen_;
+ // Use all optimizations without restrictions.
+ bool use_all_optimizations_;
+
DISALLOW_COPY_AND_ASSIGN(InstructionSimplifier);
};
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index ec3b8c4..424fbd9 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -83,6 +83,7 @@
return HInliner::kInlinerPassName;
case OptimizationPass::kSelectGenerator:
return HSelectGenerator::kSelectGeneratorPassName;
+ case OptimizationPass::kAggressiveInstructionSimplifier:
case OptimizationPass::kInstructionSimplifier:
return InstructionSimplifier::kInstructionSimplifierPassName;
case OptimizationPass::kCHAGuardOptimization:
@@ -248,6 +249,13 @@
case OptimizationPass::kInstructionSimplifier:
opt = new (allocator) InstructionSimplifier(graph, codegen, stats, pass_name);
break;
+ case OptimizationPass::kAggressiveInstructionSimplifier:
+ opt = new (allocator) InstructionSimplifier(graph,
+ codegen,
+ stats,
+ pass_name,
+ /* use_all_optimizations_ = */ true);
+ break;
case OptimizationPass::kCHAGuardOptimization:
opt = new (allocator) CHAGuardOptimization(graph, pass_name);
break;
diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h
index 4a515bc..f8aea96 100644
--- a/compiler/optimizing/optimization.h
+++ b/compiler/optimizing/optimization.h
@@ -66,6 +66,7 @@
// field is preferred over a string lookup at places where performance matters.
// TODO: generate this table and lookup methods below automatically?
enum class OptimizationPass {
+ kAggressiveInstructionSimplifier,
kBoundsCheckElimination,
kCHAGuardOptimization,
kCodeSinking,
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 45d31ba..8d4aa9f 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -643,7 +643,7 @@
// Simplification.
OptDef(OptimizationPass::kConstantFolding,
"constant_folding$after_bce"),
- OptDef(OptimizationPass::kInstructionSimplifier,
+ OptDef(OptimizationPass::kAggressiveInstructionSimplifier,
"instruction_simplifier$after_bce"),
// Other high-level optimizations.
OptDef(OptimizationPass::kSideEffectsAnalysis,
@@ -656,7 +656,7 @@
// 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.
- OptDef(OptimizationPass::kInstructionSimplifier,
+ OptDef(OptimizationPass::kAggressiveInstructionSimplifier,
"instruction_simplifier$before_codegen"),
// Eliminate constructor fences after code sinking to avoid
// complicated sinking logic to split a fence with many inputs.