From 93445689c714e53cabf347da4321ecf3023e926c Mon Sep 17 00:00:00 2001 From: Roland Levillain Date: Mon, 6 Oct 2014 19:24:02 +0100 Subject: [PATCH] Fix and improve static evaluation of constant expressions. - Fix the definition of art::HSub::Evaluate. - Qualify Evaluate methods as OVERRIDE. - Evaluate comparisons in a deterministic way: if a comparison is true, always return 1 (instead of letting the compiler return any non-null value). - Better exercise static evaluation of constant expressions in compiler/optimizing/constant_propagation_test.cc. Change-Id: I13d0862e5f4eba1275016fb8c3c17e9aff54408b --- compiler/optimizing/constant_propagation_test.cc | 145 +++++++++++++++++++---- compiler/optimizing/nodes.h | 69 ++++++++--- 2 files changed, 173 insertions(+), 41 deletions(-) diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc index d08d14db0..342777a49 100644 --- a/compiler/optimizing/constant_propagation_test.cc +++ b/compiler/optimizing/constant_propagation_test.cc @@ -14,6 +14,8 @@ * limitations under the License. */ +#include + #include "constant_propagation.h" #include "dead_code_elimination.h" #include "pretty_printer.h" @@ -28,6 +30,7 @@ static void TestCode(const uint16_t* data, const std::string& expected_before, const std::string& expected_after_cp, const std::string& expected_after_dce, + std::function check_after_cp, Primitive::Type return_type = Primitive::kPrimInt) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -49,6 +52,8 @@ static void TestCode(const uint16_t* data, std::string actual_after_cp = printer_after_cp.str(); ASSERT_EQ(expected_after_cp, actual_after_cp); + check_after_cp(graph); + DeadCodeElimination(graph).Run(); StringPrettyPrinter printer_after_dce(graph); @@ -101,6 +106,13 @@ TEST(ConstantPropagation, IntConstantFoldingOnAddition1) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the value of the computed constant. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst->IsIntConstant()); + ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 3: IntConstant\n", removed }, @@ -108,7 +120,11 @@ TEST(ConstantPropagation, IntConstantFoldingOnAddition1) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp); } /** @@ -166,6 +182,19 @@ TEST(ConstantPropagation, IntConstantFoldingOnAddition2) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the values of the computed constants. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst1->IsIntConstant()); + ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 3); + HInstruction* inst2 = inst1->GetNext(); + ASSERT_TRUE(inst2->IsIntConstant()); + ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 7); + HInstruction* inst3 = inst2->GetNext(); + ASSERT_TRUE(inst3->IsIntConstant()); + ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 10); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 3: IntConstant\n", removed }, @@ -177,7 +206,11 @@ TEST(ConstantPropagation, IntConstantFoldingOnAddition2) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp); } /** @@ -219,6 +252,13 @@ TEST(ConstantPropagation, IntConstantFoldingOnSubtraction) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the value of the computed constant. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst->IsIntConstant()); + ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 3: IntConstant\n", removed }, @@ -226,7 +266,11 @@ TEST(ConstantPropagation, IntConstantFoldingOnSubtraction) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp); } #define SIX_REGISTERS_CODE_ITEM(...) \ @@ -273,6 +317,13 @@ TEST(ConstantPropagation, LongConstantFoldingOnAddition) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the value of the computed constant. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst->IsLongConstant()); + ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 6: LongConstant\n", removed }, @@ -280,7 +331,12 @@ TEST(ConstantPropagation, LongConstantFoldingOnAddition) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce, Primitive::kPrimLong); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp, + Primitive::kPrimLong); } /** @@ -324,6 +380,13 @@ TEST(ConstantPropagation, LongConstantFoldingOnSubtraction) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the value of the computed constant. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst->IsLongConstant()); + ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 6: LongConstant\n", removed }, @@ -331,7 +394,12 @@ TEST(ConstantPropagation, LongConstantFoldingOnSubtraction) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce, Primitive::kPrimLong); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp, + Primitive::kPrimLong); } /** @@ -371,26 +439,26 @@ TEST(ConstantPropagation, IntConstantFoldingAndJumps) { std::string expected_before = "BasicBlock 0, succ: 1\n" - " 3: IntConstant [9]\n" - " 5: IntConstant [9]\n" - " 13: IntConstant [14]\n" - " 18: IntConstant [19]\n" - " 24: IntConstant [25]\n" + " 3: IntConstant [9]\n" // v0 <- 0 + " 5: IntConstant [9]\n" // v1 <- 1 + " 13: IntConstant [14]\n" // const 3 + " 18: IntConstant [19]\n" // const 2 + " 24: IntConstant [25]\n" // const 4 " 30: SuspendCheck\n" " 31: Goto 1\n" "BasicBlock 1, pred: 0, succ: 3\n" - " 9: Add(3, 5) [19]\n" - " 11: Goto 3\n" - "BasicBlock 2, pred: 3, succ: 4\n" - " 14: Add(19, 13) [25]\n" - " 16: Goto 4\n" - "BasicBlock 3, pred: 1, succ: 2\n" - " 19: Add(9, 18) [14]\n" + " 9: Add(3, 5) [19]\n" // v2 <- v0 + v1 = 0 + 1 = 1 + " 11: Goto 3\n" // goto L2 + "BasicBlock 2, pred: 3, succ: 4\n" // L1: + " 14: Add(19, 13) [25]\n" // v1 <- v0 + 3 = 3 + 3 = 6 + " 16: Goto 4\n" // goto L3 + "BasicBlock 3, pred: 1, succ: 2\n" // L2: + " 19: Add(9, 18) [14]\n" // v0 <- v2 + 2 = 1 + 2 = 3 " 21: SuspendCheck\n" - " 22: Goto 2\n" - "BasicBlock 4, pred: 2, succ: 5\n" - " 25: Add(14, 24) [28]\n" - " 28: Return(25)\n" + " 22: Goto 2\n" // goto L1 + "BasicBlock 4, pred: 2, succ: 5\n" // L3: + " 25: Add(14, 24) [28]\n" // v2 <- v1 + 4 = 6 + 4 = 10 + " 28: Return(25)\n" // return v2 "BasicBlock 5, pred: 4\n" " 29: Exit\n"; @@ -409,6 +477,22 @@ TEST(ConstantPropagation, IntConstantFoldingAndJumps) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the values of the computed constants. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst1 = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst1->IsIntConstant()); + ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 1); + HInstruction* inst2 = graph->GetBlock(2)->GetFirstInstruction(); + ASSERT_TRUE(inst2->IsIntConstant()); + ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 6); + HInstruction* inst3 = graph->GetBlock(3)->GetFirstInstruction(); + ASSERT_TRUE(inst3->IsIntConstant()); + ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3); + HInstruction* inst4 = graph->GetBlock(4)->GetFirstInstruction(); + ASSERT_TRUE(inst4->IsIntConstant()); + ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 10); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 3: IntConstant\n", removed }, @@ -419,7 +503,11 @@ TEST(ConstantPropagation, IntConstantFoldingAndJumps) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp); } @@ -474,6 +562,13 @@ TEST(ConstantPropagation, ConstantCondition) { }; std::string expected_after_cp = Patch(expected_before, expected_cp_diff); + // Check the values of the computed constants. + auto check_after_cp = [](HGraph* graph) { + HInstruction* inst = graph->GetBlock(1)->GetFirstInstruction(); + ASSERT_TRUE(inst->IsIntConstant()); + ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1); + }; + // Expected difference after dead code elimination. diff_t expected_dce_diff = { { " 3: IntConstant [15, 22]\n", " 3: IntConstant [22]\n" }, @@ -482,7 +577,11 @@ TEST(ConstantPropagation, ConstantCondition) { }; std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff); - TestCode(data, expected_before, expected_after_cp, expected_after_dce); + TestCode(data, + expected_before, + expected_after_cp, + expected_after_dce, + check_after_cp); } } // namespace art diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 3d65366c4..fc5b06d0d 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -93,6 +93,7 @@ class HGraph : public ArenaObject { ArenaAllocator* GetArena() const { return arena_; } const GrowableArray& GetBlocks() const { return blocks_; } + HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); } HBasicBlock* GetEntryBlock() const { return entry_block_; } HBasicBlock* GetExitBlock() const { return exit_block_; } @@ -1143,8 +1144,12 @@ class HEqual : public HCondition { HEqual(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x == y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x == y ? 1 : 0; + } DECLARE_INSTRUCTION(Equal); @@ -1161,8 +1166,12 @@ class HNotEqual : public HCondition { HNotEqual(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x != y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x != y ? 1 : 0; + } DECLARE_INSTRUCTION(NotEqual); @@ -1179,8 +1188,12 @@ class HLessThan : public HCondition { HLessThan(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x < y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x < y ? 1 : 0; + } DECLARE_INSTRUCTION(LessThan); @@ -1197,8 +1210,12 @@ class HLessThanOrEqual : public HCondition { HLessThanOrEqual(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x <= y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x <= y ? 1 : 0; + } DECLARE_INSTRUCTION(LessThanOrEqual); @@ -1215,8 +1232,12 @@ class HGreaterThan : public HCondition { HGreaterThan(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x > y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x > y ? 1 : 0; + } DECLARE_INSTRUCTION(GreaterThan); @@ -1233,8 +1254,12 @@ class HGreaterThanOrEqual : public HCondition { HGreaterThanOrEqual(HInstruction* first, HInstruction* second) : HCondition(first, second) {} - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x >= y ? 1 : 0; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x >= y ? 1 : 0; + } DECLARE_INSTRUCTION(GreaterThanOrEqual); @@ -1257,13 +1282,13 @@ class HCompare : public HBinaryOperation { DCHECK_EQ(type, second->GetType()); } - virtual int32_t Evaluate(int32_t x, int32_t y) const { + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x == y ? 0 : x > y ? 1 : -1; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x == y ? 0 : x > y ? 1 : @@ -1490,8 +1515,12 @@ class HAdd : public HBinaryOperation { virtual bool IsCommutative() { return true; } - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x + y; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x + y; + } DECLARE_INSTRUCTION(Add); @@ -1506,8 +1535,12 @@ class HSub : public HBinaryOperation { virtual bool IsCommutative() { return false; } - virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } - virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } + virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { + return x - y; + } + virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { + return x - y; + } DECLARE_INSTRUCTION(Sub); -- 2.11.0