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/common-operator.h" 6 #include "src/compiler/dead-code-elimination.h" 7 #include "test/unittests/compiler/graph-reducer-unittest.h" 8 #include "test/unittests/compiler/graph-unittest.h" 9 #include "test/unittests/compiler/node-test-utils.h" 10 #include "testing/gmock-support.h" 11 12 using testing::StrictMock; 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 class DeadCodeEliminationTest : public GraphTest { 19 public: 20 explicit DeadCodeEliminationTest(int num_parameters = 4) 21 : GraphTest(num_parameters) {} 22 ~DeadCodeEliminationTest() override {} 23 24 protected: 25 Reduction Reduce(AdvancedReducer::Editor* editor, Node* node) { 26 DeadCodeElimination reducer(editor, graph(), common()); 27 return reducer.Reduce(node); 28 } 29 30 Reduction Reduce(Node* node) { 31 StrictMock<MockAdvancedReducerEditor> editor; 32 return Reduce(&editor, node); 33 } 34 }; 35 36 37 namespace { 38 39 const MachineRepresentation kMachineRepresentations[] = { 40 MachineRepresentation::kBit, MachineRepresentation::kWord8, 41 MachineRepresentation::kWord16, MachineRepresentation::kWord32, 42 MachineRepresentation::kWord64, MachineRepresentation::kFloat32, 43 MachineRepresentation::kFloat64, MachineRepresentation::kTagged}; 44 45 46 const int kMaxInputs = 16; 47 48 49 const Operator kOp0(0, Operator::kNoProperties, "Op0", 1, 1, 1, 1, 1, 1); 50 51 } // namespace 52 53 54 // ----------------------------------------------------------------------------- 55 // General dead propagation 56 57 58 TEST_F(DeadCodeEliminationTest, GeneralDeadPropagation) { 59 Node* const value = Parameter(0); 60 Node* const effect = graph()->start(); 61 Node* const dead = graph()->NewNode(common()->Dead()); 62 Node* const node = graph()->NewNode(&kOp0, value, effect, dead); 63 Reduction const r = Reduce(node); 64 ASSERT_TRUE(r.Changed()); 65 EXPECT_THAT(r.replacement(), IsDead()); 66 } 67 68 69 // ----------------------------------------------------------------------------- 70 // Branch 71 72 73 TEST_F(DeadCodeEliminationTest, BranchWithDeadControlInput) { 74 BranchHint const kHints[] = {BranchHint::kNone, BranchHint::kTrue, 75 BranchHint::kFalse}; 76 TRACED_FOREACH(BranchHint, hint, kHints) { 77 Reduction const r = 78 Reduce(graph()->NewNode(common()->Branch(hint), Parameter(0), 79 graph()->NewNode(common()->Dead()))); 80 ASSERT_TRUE(r.Changed()); 81 EXPECT_THAT(r.replacement(), IsDead()); 82 } 83 } 84 85 86 // ----------------------------------------------------------------------------- 87 // IfTrue 88 89 90 TEST_F(DeadCodeEliminationTest, IfTrueWithDeadInput) { 91 Reduction const r = Reduce( 92 graph()->NewNode(common()->IfTrue(), graph()->NewNode(common()->Dead()))); 93 ASSERT_TRUE(r.Changed()); 94 EXPECT_THAT(r.replacement(), IsDead()); 95 } 96 97 98 // ----------------------------------------------------------------------------- 99 // IfFalse 100 101 102 TEST_F(DeadCodeEliminationTest, IfFalseWithDeadInput) { 103 Reduction const r = Reduce(graph()->NewNode( 104 common()->IfFalse(), graph()->NewNode(common()->Dead()))); 105 ASSERT_TRUE(r.Changed()); 106 EXPECT_THAT(r.replacement(), IsDead()); 107 } 108 109 110 // ----------------------------------------------------------------------------- 111 // IfSuccess 112 113 114 TEST_F(DeadCodeEliminationTest, IfSuccessWithDeadInput) { 115 Reduction const r = Reduce(graph()->NewNode( 116 common()->IfSuccess(), graph()->NewNode(common()->Dead()))); 117 ASSERT_TRUE(r.Changed()); 118 EXPECT_THAT(r.replacement(), IsDead()); 119 } 120 121 122 // ----------------------------------------------------------------------------- 123 // IfException 124 125 126 TEST_F(DeadCodeEliminationTest, IfExceptionWithDeadControlInput) { 127 IfExceptionHint const kHints[] = {IfExceptionHint::kLocallyCaught, 128 IfExceptionHint::kLocallyUncaught}; 129 TRACED_FOREACH(IfExceptionHint, hint, kHints) { 130 Reduction const r = 131 Reduce(graph()->NewNode(common()->IfException(hint), graph()->start(), 132 graph()->NewNode(common()->Dead()))); 133 ASSERT_TRUE(r.Changed()); 134 EXPECT_THAT(r.replacement(), IsDead()); 135 } 136 } 137 138 139 // ----------------------------------------------------------------------------- 140 // End 141 142 143 TEST_F(DeadCodeEliminationTest, EndWithDeadAndStart) { 144 Node* const dead = graph()->NewNode(common()->Dead()); 145 Node* const start = graph()->start(); 146 Reduction const r = Reduce(graph()->NewNode(common()->End(2), dead, start)); 147 ASSERT_TRUE(r.Changed()); 148 EXPECT_THAT(r.replacement(), IsEnd(start)); 149 } 150 151 152 TEST_F(DeadCodeEliminationTest, EndWithOnlyDeadInputs) { 153 Node* inputs[kMaxInputs]; 154 TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) { 155 for (int i = 0; i < input_count; ++i) { 156 inputs[i] = graph()->NewNode(common()->Dead()); 157 } 158 Reduction const r = Reduce( 159 graph()->NewNode(common()->End(input_count), input_count, inputs)); 160 ASSERT_TRUE(r.Changed()); 161 EXPECT_THAT(r.replacement(), IsDead()); 162 } 163 } 164 165 166 // ----------------------------------------------------------------------------- 167 // Merge 168 169 170 TEST_F(DeadCodeEliminationTest, MergeWithOnlyDeadInputs) { 171 Node* inputs[kMaxInputs + 1]; 172 TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) { 173 for (int i = 0; i < input_count; ++i) { 174 inputs[i] = graph()->NewNode(common()->Dead()); 175 } 176 Reduction const r = Reduce( 177 graph()->NewNode(common()->Merge(input_count), input_count, inputs)); 178 ASSERT_TRUE(r.Changed()); 179 EXPECT_THAT(r.replacement(), IsDead()); 180 } 181 } 182 183 184 TEST_F(DeadCodeEliminationTest, MergeWithOneLiveAndOneDeadInput) { 185 Node* const v0 = Parameter(0); 186 Node* const v1 = Parameter(1); 187 Node* const c0 = 188 graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start()); 189 Node* const c1 = graph()->NewNode(common()->Dead()); 190 Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0); 191 Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1); 192 Node* const merge = graph()->NewNode(common()->Merge(2), c0, c1); 193 Node* const phi = graph()->NewNode( 194 common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, merge); 195 Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, merge); 196 StrictMock<MockAdvancedReducerEditor> editor; 197 EXPECT_CALL(editor, Replace(phi, v0)); 198 EXPECT_CALL(editor, Replace(ephi, e0)); 199 Reduction const r = Reduce(&editor, merge); 200 ASSERT_TRUE(r.Changed()); 201 EXPECT_EQ(c0, r.replacement()); 202 } 203 204 205 TEST_F(DeadCodeEliminationTest, MergeWithTwoLiveAndTwoDeadInputs) { 206 Node* const v0 = Parameter(0); 207 Node* const v1 = Parameter(1); 208 Node* const v2 = Parameter(2); 209 Node* const v3 = Parameter(3); 210 Node* const c0 = 211 graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start()); 212 Node* const c1 = graph()->NewNode(common()->Dead()); 213 Node* const c2 = graph()->NewNode(common()->Dead()); 214 Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0); 215 Node* const e0 = graph()->start(); 216 Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0); 217 Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0); 218 Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3); 219 Node* const merge = graph()->NewNode(common()->Merge(4), c0, c1, c2, c3); 220 Node* const phi = graph()->NewNode( 221 common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, merge); 222 Node* const ephi = 223 graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, merge); 224 StrictMock<MockAdvancedReducerEditor> editor; 225 EXPECT_CALL(editor, Revisit(phi)); 226 EXPECT_CALL(editor, Revisit(ephi)); 227 Reduction const r = Reduce(&editor, merge); 228 ASSERT_TRUE(r.Changed()); 229 EXPECT_THAT(r.replacement(), IsMerge(c0, c3)); 230 EXPECT_THAT(phi, 231 IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement())); 232 EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement())); 233 } 234 235 236 // ----------------------------------------------------------------------------- 237 // Loop 238 239 240 TEST_F(DeadCodeEliminationTest, LoopWithDeadFirstInput) { 241 Node* inputs[kMaxInputs + 1]; 242 TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) { 243 inputs[0] = graph()->NewNode(common()->Dead()); 244 for (int i = 1; i < input_count; ++i) { 245 inputs[i] = graph()->start(); 246 } 247 Reduction const r = Reduce( 248 graph()->NewNode(common()->Loop(input_count), input_count, inputs)); 249 ASSERT_TRUE(r.Changed()); 250 EXPECT_THAT(r.replacement(), IsDead()); 251 } 252 } 253 254 255 TEST_F(DeadCodeEliminationTest, LoopWithOnlyDeadInputs) { 256 Node* inputs[kMaxInputs + 1]; 257 TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) { 258 for (int i = 0; i < input_count; ++i) { 259 inputs[i] = graph()->NewNode(common()->Dead()); 260 } 261 Reduction const r = Reduce( 262 graph()->NewNode(common()->Loop(input_count), input_count, inputs)); 263 ASSERT_TRUE(r.Changed()); 264 EXPECT_THAT(r.replacement(), IsDead()); 265 } 266 } 267 268 269 TEST_F(DeadCodeEliminationTest, LoopWithOneLiveAndOneDeadInput) { 270 Node* const v0 = Parameter(0); 271 Node* const v1 = Parameter(1); 272 Node* const c0 = 273 graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start()); 274 Node* const c1 = graph()->NewNode(common()->Dead()); 275 Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0); 276 Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1); 277 Node* const loop = graph()->NewNode(common()->Loop(2), c0, c1); 278 Node* const phi = graph()->NewNode( 279 common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, loop); 280 Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, loop); 281 Node* const terminate = graph()->NewNode(common()->Terminate(), ephi, loop); 282 StrictMock<MockAdvancedReducerEditor> editor; 283 EXPECT_CALL(editor, Replace(phi, v0)); 284 EXPECT_CALL(editor, Replace(ephi, e0)); 285 EXPECT_CALL(editor, Replace(terminate, IsDead())); 286 Reduction const r = Reduce(&editor, loop); 287 ASSERT_TRUE(r.Changed()); 288 EXPECT_EQ(c0, r.replacement()); 289 } 290 291 292 TEST_F(DeadCodeEliminationTest, LoopWithTwoLiveAndTwoDeadInputs) { 293 Node* const v0 = Parameter(0); 294 Node* const v1 = Parameter(1); 295 Node* const v2 = Parameter(2); 296 Node* const v3 = Parameter(3); 297 Node* const c0 = 298 graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start()); 299 Node* const c1 = graph()->NewNode(common()->Dead()); 300 Node* const c2 = graph()->NewNode(common()->Dead()); 301 Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0); 302 Node* const e0 = graph()->start(); 303 Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0); 304 Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0); 305 Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3); 306 Node* const loop = graph()->NewNode(common()->Loop(4), c0, c1, c2, c3); 307 Node* const phi = graph()->NewNode( 308 common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, loop); 309 Node* const ephi = 310 graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, loop); 311 StrictMock<MockAdvancedReducerEditor> editor; 312 EXPECT_CALL(editor, Revisit(phi)); 313 EXPECT_CALL(editor, Revisit(ephi)); 314 Reduction const r = Reduce(&editor, loop); 315 ASSERT_TRUE(r.Changed()); 316 EXPECT_THAT(r.replacement(), IsLoop(c0, c3)); 317 EXPECT_THAT(phi, 318 IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement())); 319 EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement())); 320 } 321 322 323 // ----------------------------------------------------------------------------- 324 // Phi 325 326 327 TEST_F(DeadCodeEliminationTest, PhiWithDeadControlInput) { 328 Node* inputs[kMaxInputs + 1]; 329 TRACED_FOREACH(MachineRepresentation, rep, kMachineRepresentations) { 330 TRACED_FORRANGE(int, input_count, 1, kMaxInputs) { 331 for (int i = 0; i < input_count; ++i) { 332 inputs[i] = Parameter(i); 333 } 334 inputs[input_count] = graph()->NewNode(common()->Dead()); 335 Reduction const r = Reduce(graph()->NewNode( 336 common()->Phi(rep, input_count), input_count + 1, inputs)); 337 ASSERT_TRUE(r.Changed()); 338 EXPECT_THAT(r.replacement(), IsDead()); 339 } 340 } 341 } 342 343 344 // ----------------------------------------------------------------------------- 345 // EffectPhi 346 347 348 TEST_F(DeadCodeEliminationTest, EffectPhiWithDeadControlInput) { 349 Node* inputs[kMaxInputs + 1]; 350 TRACED_FORRANGE(int, input_count, 1, kMaxInputs) { 351 for (int i = 0; i < input_count; ++i) { 352 inputs[i] = graph()->start(); 353 } 354 inputs[input_count] = graph()->NewNode(common()->Dead()); 355 Reduction const r = Reduce(graph()->NewNode( 356 common()->EffectPhi(input_count), input_count + 1, inputs)); 357 ASSERT_TRUE(r.Changed()); 358 EXPECT_THAT(r.replacement(), IsDead()); 359 } 360 } 361 362 363 // ----------------------------------------------------------------------------- 364 // Terminate 365 366 367 TEST_F(DeadCodeEliminationTest, TerminateWithDeadControlInput) { 368 Reduction const r = 369 Reduce(graph()->NewNode(common()->Terminate(), graph()->start(), 370 graph()->NewNode(common()->Dead()))); 371 ASSERT_TRUE(r.Changed()); 372 EXPECT_THAT(r.replacement(), IsDead()); 373 } 374 375 } // namespace compiler 376 } // namespace internal 377 } // namespace v8 378
