ART: Add div-zero check elimination to LVN/GVN
GVN has been updated to also consider div/rem zero check elimination.
This means that whenever a divisor is used in two sequential divisions,
the second division will surely not throw exception.
The algorithm has been updated to work on global level by considering
splits and merges. Obviously, if "div_zero" checked on one path but
not the other, at merge point consider that division has not been
eliminated.
One big deficiency of this algorithm is that it does not consider
literals in the divisor. Namely, in cases where the operand is a literal
or a constant (literal created by another bytecode), it does not mark as
divide by zero checked. However, in reality this is not an issue
because none of the backends generate the divide by zero check when
the constant value is known.
Issue: CAR-868
Category: device enablement
Domain: AOSP.ART-ME
Origin: internal
Upstream-Candidate: yes
Change-Id: I617569055c73a45e13e2a83392b99b48f4e33362
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>
diff --git a/compiler/dex/global_value_numbering_test.cc b/compiler/dex/global_value_numbering_test.cc
index 35d5b99..3060e67 100644
--- a/compiler/dex/global_value_numbering_test.cc
+++ b/compiler/dex/global_value_numbering_test.cc
@@ -131,6 +131,8 @@
{ bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } }
#define DEF_PHI2(bb, reg, src1, src2) \
{ bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } }
+#define DEF_DIV_REM(bb, opcode, result, dividend, divisor) \
+ { bb, opcode, 0u, 0u, 2, { dividend, divisor }, 1, { result } }
void DoPrepareIFields(const IFieldDef* defs, size_t count) {
cu_.mir_graph->ifield_lowering_infos_.clear();
@@ -2213,4 +2215,45 @@
PerformGVN();
}
+TEST_F(GlobalValueNumberingTestDiamond, DivZeroCheckDiamond) {
+ static const MIRDef mirs[] = {
+ DEF_DIV_REM(3u, Instruction::DIV_INT, 1u, 20u, 21u),
+ DEF_DIV_REM(3u, Instruction::DIV_INT, 2u, 24u, 21u),
+ DEF_DIV_REM(3u, Instruction::DIV_INT, 3u, 20u, 23u),
+ DEF_DIV_REM(4u, Instruction::DIV_INT, 4u, 24u, 22u),
+ DEF_DIV_REM(4u, Instruction::DIV_INT, 9u, 24u, 25u),
+ DEF_DIV_REM(5u, Instruction::DIV_INT, 5u, 24u, 21u),
+ DEF_DIV_REM(5u, Instruction::DIV_INT, 10u, 24u, 26u),
+ DEF_PHI2(6u, 27u, 25u, 26u),
+ DEF_DIV_REM(6u, Instruction::DIV_INT, 12u, 20u, 27u),
+ DEF_DIV_REM(6u, Instruction::DIV_INT, 6u, 24u, 21u),
+ DEF_DIV_REM(6u, Instruction::DIV_INT, 7u, 20u, 23u),
+ DEF_DIV_REM(6u, Instruction::DIV_INT, 8u, 20u, 22u),
+ };
+
+ static const bool expected_ignore_div_zero_check[] = {
+ false, // New divisor seen.
+ true, // Eliminated since it has first divisor as first one.
+ false, // New divisor seen.
+ false, // New divisor seen.
+ false, // New divisor seen.
+ true, // Eliminated in dominating block.
+ false, // New divisor seen.
+ false, // Phi node.
+ true, // Eliminated on both sides of diamond and merged via phi.
+ true, // Eliminated in dominating block.
+ true, // Eliminated in dominating block.
+ false, // Only eliminated on one path of diamond.
+ };
+
+ PrepareMIRs(mirs);
+ PerformGVN();
+ PerformGVNCodeModifications();
+ ASSERT_EQ(arraysize(expected_ignore_div_zero_check), mir_count_);
+ for (size_t i = 0u; i != mir_count_; ++i) {
+ int expected = expected_ignore_div_zero_check[i] ? MIR_IGNORE_DIV_ZERO_CHECK : 0u;
+ EXPECT_EQ(expected, mirs_[i].optimization_flags) << i;
+ }
+}
+
} // namespace art