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 3 // found in the LICENSE file. 4 5 #include "src/compiler/branch-elimination.h" 6 #include "src/compiler/js-graph.h" 7 #include "src/compiler/linkage.h" 8 #include "src/compiler/node-properties.h" 9 #include "test/unittests/compiler/compiler-test-utils.h" 10 #include "test/unittests/compiler/graph-unittest.h" 11 #include "test/unittests/compiler/node-test-utils.h" 12 #include "testing/gmock-support.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 class BranchEliminationTest : public TypedGraphTest { 19 public: 20 BranchEliminationTest() 21 : machine_(zone(), MachineType::PointerRepresentation(), 22 MachineOperatorBuilder::kNoFlags) {} 23 24 MachineOperatorBuilder* machine() { return &machine_; } 25 26 void Reduce() { 27 JSOperatorBuilder javascript(zone()); 28 JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr, 29 machine()); 30 GraphReducer graph_reducer(zone(), graph(), jsgraph.Dead()); 31 BranchElimination branch_condition_elimination(&graph_reducer, &jsgraph, 32 zone()); 33 graph_reducer.AddReducer(&branch_condition_elimination); 34 graph_reducer.ReduceGraph(); 35 } 36 37 private: 38 MachineOperatorBuilder machine_; 39 }; 40 41 42 TEST_F(BranchEliminationTest, NestedBranchSameTrue) { 43 // { return (x ? (x ? 1 : 2) : 3; } 44 // should be reduced to 45 // { return (x ? 1 : 3; } 46 Node* condition = Parameter(0); 47 Node* outer_branch = 48 graph()->NewNode(common()->Branch(), condition, graph()->start()); 49 50 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); 51 Node* inner_branch = 52 graph()->NewNode(common()->Branch(), condition, outer_if_true); 53 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); 54 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); 55 Node* inner_merge = 56 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); 57 Node* inner_phi = 58 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 59 Int32Constant(1), Int32Constant(2), inner_merge); 60 61 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); 62 Node* outer_merge = 63 graph()->NewNode(common()->Merge(2), inner_merge, outer_if_false); 64 Node* outer_phi = 65 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 66 inner_phi, Int32Constant(3), outer_merge); 67 68 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), 69 outer_merge); 70 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); 71 72 Reduce(); 73 74 // Outer branch should not be rewritten, the inner branch should be discarded. 75 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); 76 EXPECT_THAT(inner_phi, 77 IsPhi(MachineRepresentation::kWord32, IsInt32Constant(1), 78 IsInt32Constant(2), IsMerge(outer_if_true, IsDead()))); 79 } 80 81 82 TEST_F(BranchEliminationTest, NestedBranchSameFalse) { 83 // { return (x ? 1 : (x ? 2 : 3); } 84 // should be reduced to 85 // { return (x ? 1 : 3; } 86 Node* condition = Parameter(0); 87 Node* outer_branch = 88 graph()->NewNode(common()->Branch(), condition, graph()->start()); 89 90 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); 91 92 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); 93 Node* inner_branch = 94 graph()->NewNode(common()->Branch(), condition, outer_if_false); 95 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); 96 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); 97 Node* inner_merge = 98 graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false); 99 Node* inner_phi = 100 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 101 Int32Constant(2), Int32Constant(3), inner_merge); 102 103 Node* outer_merge = 104 graph()->NewNode(common()->Merge(2), outer_if_true, inner_merge); 105 Node* outer_phi = 106 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 107 Int32Constant(1), inner_phi, outer_merge); 108 109 Node* ret = graph()->NewNode(common()->Return(), outer_phi, graph()->start(), 110 outer_merge); 111 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); 112 113 Reduce(); 114 115 // Outer branch should not be rewritten, the inner branch should be discarded. 116 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); 117 EXPECT_THAT(inner_phi, 118 IsPhi(MachineRepresentation::kWord32, IsInt32Constant(2), 119 IsInt32Constant(3), IsMerge(IsDead(), outer_if_false))); 120 } 121 122 123 TEST_F(BranchEliminationTest, BranchAfterDiamond) { 124 // { var y = x ? 1 : 2; return y + x ? 3 : 4; } 125 // should not be reduced. 126 Node* condition = Parameter(0); 127 128 Node* branch1 = 129 graph()->NewNode(common()->Branch(), condition, graph()->start()); 130 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); 131 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); 132 Node* merge1 = graph()->NewNode(common()->Merge(2), if_true1, if_false1); 133 Node* phi1 = 134 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 135 Int32Constant(1), Int32Constant(2), merge1); 136 137 Node* branch2 = graph()->NewNode(common()->Branch(), condition, merge1); 138 Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2); 139 Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2); 140 Node* merge2 = graph()->NewNode(common()->Merge(2), if_true2, if_false2); 141 Node* phi2 = 142 graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), 143 Int32Constant(3), Int32Constant(4), merge1); 144 145 146 Node* add = graph()->NewNode(machine()->Int32Add(), phi1, phi2); 147 Node* ret = 148 graph()->NewNode(common()->Return(), add, graph()->start(), merge2); 149 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); 150 151 Reduce(); 152 153 // Outer branch should not be rewritten, the inner branch condition should 154 // be true. 155 EXPECT_THAT(branch1, IsBranch(condition, graph()->start())); 156 EXPECT_THAT(branch2, IsBranch(condition, merge1)); 157 } 158 159 160 TEST_F(BranchEliminationTest, BranchInsideLoopSame) { 161 // if (x) while (x) { return 2; } else { return 1; } 162 // should be rewritten to 163 // if (x) while (true) { return 2; } else { return 1; } 164 165 Node* condition = Parameter(0); 166 167 Node* outer_branch = 168 graph()->NewNode(common()->Branch(), condition, graph()->start()); 169 Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch); 170 171 172 Node* loop = graph()->NewNode(common()->Loop(1), outer_if_true); 173 Node* effect = 174 graph()->NewNode(common()->EffectPhi(1), graph()->start(), loop); 175 176 Node* inner_branch = graph()->NewNode(common()->Branch(), condition, loop); 177 178 Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch); 179 Node* ret1 = graph()->NewNode(common()->Return(), Int32Constant(2), effect, 180 inner_if_true); 181 182 Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch); 183 loop->AppendInput(zone(), inner_if_false); 184 NodeProperties::ChangeOp(loop, common()->Loop(2)); 185 effect->InsertInput(zone(), 1, effect); 186 NodeProperties::ChangeOp(effect, common()->EffectPhi(2)); 187 188 Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch); 189 Node* outer_merge = 190 graph()->NewNode(common()->Merge(2), loop, outer_if_false); 191 Node* outer_ephi = graph()->NewNode(common()->EffectPhi(2), effect, 192 graph()->start(), outer_merge); 193 194 Node* ret2 = graph()->NewNode(common()->Return(), Int32Constant(1), 195 outer_ephi, outer_merge); 196 197 Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop); 198 graph()->SetEnd(graph()->NewNode(common()->End(3), ret1, ret2, terminate)); 199 200 Reduce(); 201 202 // Outer branch should not be rewritten, the inner branch should be discarded. 203 EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start())); 204 EXPECT_THAT(ret1, IsReturn(IsInt32Constant(2), effect, loop)); 205 } 206 207 } // namespace compiler 208 } // namespace internal 209 } // namespace v8 210
