| OLD | NEW |
| 1 // Copyright 2015 the V8 project authors. All rights reserved. | 1 // Copyright 2015 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/compiler/branch-elimination.h" | 5 #include "src/compiler/branch-elimination.h" |
| 6 #include "src/compiler/js-graph.h" | 6 #include "src/compiler/js-graph.h" |
| 7 #include "src/compiler/linkage.h" | 7 #include "src/compiler/linkage.h" |
| 8 #include "src/compiler/node-properties.h" | 8 #include "src/compiler/node-properties.h" |
| 9 #include "test/unittests/compiler/compiler-test-utils.h" | 9 #include "test/unittests/compiler/compiler-test-utils.h" |
| 10 #include "test/unittests/compiler/graph-unittest.h" | 10 #include "test/unittests/compiler/graph-unittest.h" |
| 11 #include "test/unittests/compiler/node-test-utils.h" | 11 #include "test/unittests/compiler/node-test-utils.h" |
| 12 #include "testing/gmock-support.h" | 12 #include "testing/gmock-support.h" |
| 13 | 13 |
| 14 namespace v8 { | 14 namespace v8 { |
| 15 namespace internal { | 15 namespace internal { |
| 16 namespace compiler { | 16 namespace compiler { |
| 17 | 17 |
| 18 class BranchEliminationTest : public TypedGraphTest { | 18 class BranchEliminationTest : public TypedGraphTest { |
| 19 public: | 19 public: |
| 20 BranchEliminationTest() | 20 BranchEliminationTest() |
| 21 : machine_(zone(), kMachPtr, MachineOperatorBuilder::kNoFlags) {} | 21 : machine_(zone(), MachineType::PointerRepresentation(), |
| 22 MachineOperatorBuilder::kNoFlags) {} |
| 22 | 23 |
| 23 MachineOperatorBuilder* machine() { return &machine_; } | 24 MachineOperatorBuilder* machine() { return &machine_; } |
| 24 | 25 |
| 25 void Reduce() { | 26 void Reduce() { |
| 26 JSOperatorBuilder javascript(zone()); | 27 JSOperatorBuilder javascript(zone()); |
| 27 JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr, | 28 JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr, |
| 28 machine()); | 29 machine()); |
| 29 GraphReducer graph_reducer(zone(), graph(), jsgraph.Dead()); | 30 GraphReducer graph_reducer(zone(), graph(), jsgraph.Dead()); |
| 30 BranchElimination branch_condition_elimination(&graph_reducer, &jsgraph, | 31 BranchElimination branch_condition_elimination(&graph_reducer, &jsgraph, |
| 31 zone()); | 32 zone()); |
| (...skipping 15 matching lines...) Expand all Loading... |
| 47 graph()->NewNode(common()->Branch(), condition, graph()->start()); | 48 graph()->NewNode(common()->Branch(), condition, graph()->start()); |
| 48 | 49 |
| 49 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); | 50 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); |
| 50 Node* inner_branch = | 51 Node* inner_branch = |
| 51 graph()->NewNode(common()->Branch(), condition, outer_if_true); | 52 graph()->NewNode(common()->Branch(), condition, outer_if_true); |
| 52 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); | 53 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); |
| 53 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); | 54 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); |
| 54 Node* inner_merge = | 55 Node* inner_merge = |
| 55 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); | 56 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); |
| 56 Node* inner_phi = | 57 Node* inner_phi = |
| 57 graph()->NewNode(common()->Phi(kMachInt32, 2), Int32Constant(1), | 58 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 58 Int32Constant(2), inner_merge); | 59 Int32Constant(1), Int32Constant(2), inner_merge); |
| 59 | 60 |
| 60 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); | 61 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); |
| 61 Node* outer_merge = | 62 Node* outer_merge = |
| 62 graph()->NewNode(common()->Merge(2), inner_merge, outer_if_false); | 63 graph()->NewNode(common()->Merge(2), inner_merge, outer_if_false); |
| 63 Node* outer_phi = graph()->NewNode(common()->Phi(kMachInt32, 2), inner_phi, | 64 Node* outer_phi = |
| 64 Int32Constant(3), outer_merge); | 65 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 66 inner_phi, Int32Constant(3), outer_merge); |
| 65 | 67 |
| 66 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), | 68 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), |
| 67 outer_merge); | 69 outer_merge); |
| 68 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); | 70 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); |
| 69 | 71 |
| 70 Reduce(); | 72 Reduce(); |
| 71 | 73 |
| 72 // Outer branch should not be rewritten, the inner branch should be discarded. | 74 // Outer branch should not be rewritten, the inner branch should be discarded. |
| 73 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); | 75 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); |
| 74 EXPECT_THAT(inner_phi, | 76 EXPECT_THAT(inner_phi, |
| 75 IsPhi(kMachInt32, IsInt32Constant(1), IsInt32Constant(2), | 77 IsPhi(MachineRepresentation::kWord32, IsInt32Constant(1), |
| 76 IsMerge(outer_if_true, IsDead()))); | 78 IsInt32Constant(2), IsMerge(outer_if_true, IsDead()))); |
| 77 } | 79 } |
| 78 | 80 |
| 79 | 81 |
| 80 TEST_F(BranchEliminationTest, NestedBranchSameFalse) { | 82 TEST_F(BranchEliminationTest, NestedBranchSameFalse) { |
| 81 // { return (x ? 1 : (x ? 2 : 3); } | 83 // { return (x ? 1 : (x ? 2 : 3); } |
| 82 // should be reduced to | 84 // should be reduced to |
| 83 // { return (x ? 1 : 3; } | 85 // { return (x ? 1 : 3; } |
| 84 Node* condition = Parameter(0); | 86 Node* condition = Parameter(0); |
| 85 Node* outer_branch = | 87 Node* outer_branch = |
| 86 graph()->NewNode(common()->Branch(), condition, graph()->start()); | 88 graph()->NewNode(common()->Branch(), condition, graph()->start()); |
| 87 | 89 |
| 88 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); | 90 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); |
| 89 | 91 |
| 90 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); | 92 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); |
| 91 Node* inner_branch = | 93 Node* inner_branch = |
| 92 graph()->NewNode(common()->Branch(), condition, outer_if_false); | 94 graph()->NewNode(common()->Branch(), condition, outer_if_false); |
| 93 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); | 95 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); |
| 94 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); | 96 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); |
| 95 Node* inner_merge = | 97 Node* inner_merge = |
| 96 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); | 98 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); |
| 97 Node* inner_phi = | 99 Node* inner_phi = |
| 98 graph()->NewNode(common()->Phi(kMachInt32, 2), Int32Constant(2), | 100 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 99 Int32Constant(3), inner_merge); | 101 Int32Constant(2), Int32Constant(3), inner_merge); |
| 100 | 102 |
| 101 Node* outer_merge = | 103 Node* outer_merge = |
| 102 graph()->NewNode(common()->Merge(2), outer_if_true, inner_merge); | 104 graph()->NewNode(common()->Merge(2), outer_if_true, inner_merge); |
| 103 Node* outer_phi = graph()->NewNode(common()->Phi(kMachInt32, 2), | 105 Node* outer_phi = |
| 104 Int32Constant(1), inner_phi, outer_merge); | 106 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 107 Int32Constant(1), inner_phi, outer_merge); |
| 105 | 108 |
| 106 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), | 109 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), |
| 107 outer_merge); | 110 outer_merge); |
| 108 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); | 111 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); |
| 109 | 112 |
| 110 Reduce(); | 113 Reduce(); |
| 111 | 114 |
| 112 // Outer branch should not be rewritten, the inner branch should be discarded. | 115 // Outer branch should not be rewritten, the inner branch should be discarded. |
| 113 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); | 116 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); |
| 114 EXPECT_THAT(inner_phi, | 117 EXPECT_THAT(inner_phi, |
| 115 IsPhi(kMachInt32, IsInt32Constant(2), IsInt32Constant(3), | 118 IsPhi(MachineRepresentation::kWord32, IsInt32Constant(2), |
| 116 IsMerge(IsDead(), outer_if_false))); | 119 IsInt32Constant(3), IsMerge(IsDead(), outer_if_false))); |
| 117 } | 120 } |
| 118 | 121 |
| 119 | 122 |
| 120 TEST_F(BranchEliminationTest, BranchAfterDiamond) { | 123 TEST_F(BranchEliminationTest, BranchAfterDiamond) { |
| 121 // { var y = x ? 1 : 2; return y + x ? 3 : 4; } | 124 // { var y = x ? 1 : 2; return y + x ? 3 : 4; } |
| 122 // should not be reduced. | 125 // should not be reduced. |
| 123 Node* condition = Parameter(0); | 126 Node* condition = Parameter(0); |
| 124 | 127 |
| 125 Node* branch1 = | 128 Node* branch1 = |
| 126 graph()->NewNode(common()->Branch(), condition, graph()->start()); | 129 graph()->NewNode(common()->Branch(), condition, graph()->start()); |
| 127 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); | 130 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); |
| 128 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); | 131 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); |
| 129 Node* merge1 = graph()->NewNode(common()->Merge(2), if_true1, if_false1); | 132 Node* merge1 = graph()->NewNode(common()->Merge(2), if_true1, if_false1); |
| 130 Node* phi1 = graph()->NewNode(common()->Phi(kMachInt32, 2), Int32Constant(1), | 133 Node* phi1 = |
| 131 Int32Constant(2), merge1); | 134 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 135 Int32Constant(1), Int32Constant(2), merge1); |
| 132 | 136 |
| 133 Node* branch2 = graph()->NewNode(common()->Branch(), condition, merge1); | 137 Node* branch2 = graph()->NewNode(common()->Branch(), condition, merge1); |
| 134 Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2); | 138 Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2); |
| 135 Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2); | 139 Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2); |
| 136 Node* merge2 = graph()->NewNode(common()->Merge(2), if_true2, if_false2); | 140 Node* merge2 = graph()->NewNode(common()->Merge(2), if_true2, if_false2); |
| 137 Node* phi2 = graph()->NewNode(common()->Phi(kMachInt32, 2), Int32Constant(3), | 141 Node* phi2 = |
| 138 Int32Constant(4), merge1); | 142 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), |
| 143 Int32Constant(3), Int32Constant(4), merge1); |
| 139 | 144 |
| 140 | 145 |
| 141 Node* add = graph()->NewNode(machine()->Int32Add(), phi1, phi2); | 146 Node* add = graph()->NewNode(machine()->Int32Add(), phi1, phi2); |
| 142 Node* ret = | 147 Node* ret = |
| 143 graph()->NewNode(common()->Return(), add, graph()->start(), merge2); | 148 graph()->NewNode(common()->Return(), add, graph()->start(), merge2); |
| 144 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); | 149 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); |
| 145 | 150 |
| 146 Reduce(); | 151 Reduce(); |
| 147 | 152 |
| 148 // Outer branch should not be rewritten, the inner branch condition should | 153 // Outer branch should not be rewritten, the inner branch condition should |
| (...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 195 Reduce(); | 200 Reduce(); |
| 196 | 201 |
| 197 // Outer branch should not be rewritten, the inner branch should be discarded. | 202 // Outer branch should not be rewritten, the inner branch should be discarded. |
| 198 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); | 203 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); |
| 199 EXPECT_THAT(ret1, IsReturn(IsInt32Constant(2), effect, loop)); | 204 EXPECT_THAT(ret1, IsReturn(IsInt32Constant(2), effect, loop)); |
| 200 } | 205 } |
| 201 | 206 |
| 202 } // namespace compiler | 207 } // namespace compiler |
| 203 } // namespace internal | 208 } // namespace internal |
| 204 } // namespace v8 | 209 } // namespace v8 |
| OLD | NEW |