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/bit-vector.h" 6 #include "src/compiler/escape-analysis.h" 7 #include "src/compiler/escape-analysis-reducer.h" 8 #include "src/compiler/graph-visualizer.h" 9 #include "src/compiler/js-graph.h" 10 #include "src/compiler/node-properties.h" 11 #include "src/compiler/simplified-operator.h" 12 #include "src/types-inl.h" 13 #include "src/zone-containers.h" 14 #include "test/unittests/compiler/graph-unittest.h" 15 16 namespace v8 { 17 namespace internal { 18 namespace compiler { 19 20 class EscapeAnalysisTest : public GraphTest { 21 public: 22 EscapeAnalysisTest() 23 : simplified_(zone()), 24 jsgraph_(isolate(), graph(), common(), nullptr, nullptr, nullptr), 25 escape_analysis_(graph(), common(), zone()), 26 effect_(graph()->start()), 27 control_(graph()->start()) {} 28 29 ~EscapeAnalysisTest() {} 30 31 EscapeAnalysis* escape_analysis() { return &escape_analysis_; } 32 33 protected: 34 void Analysis() { escape_analysis_.Run(); } 35 36 void Transformation() { 37 GraphReducer graph_reducer(zone(), graph()); 38 EscapeAnalysisReducer escape_reducer(&graph_reducer, &jsgraph_, 39 &escape_analysis_, zone()); 40 graph_reducer.AddReducer(&escape_reducer); 41 graph_reducer.ReduceGraph(); 42 } 43 44 // ---------------------------------Node Creation Helper---------------------- 45 46 Node* BeginRegion(Node* effect = nullptr) { 47 if (!effect) { 48 effect = effect_; 49 } 50 51 return effect_ = graph()->NewNode(common()->BeginRegion(), effect); 52 } 53 54 Node* FinishRegion(Node* value, Node* effect = nullptr) { 55 if (!effect) { 56 effect = effect_; 57 } 58 return effect_ = graph()->NewNode(common()->FinishRegion(), value, effect); 59 } 60 61 Node* Allocate(Node* size, Node* effect = nullptr, Node* control = nullptr) { 62 if (!effect) { 63 effect = effect_; 64 } 65 if (!control) { 66 control = control_; 67 } 68 return effect_ = graph()->NewNode(simplified()->Allocate(), size, effect, 69 control); 70 } 71 72 Node* Constant(int num) { 73 return graph()->NewNode(common()->NumberConstant(num)); 74 } 75 76 Node* Store(const FieldAccess& access, Node* allocation, Node* value, 77 Node* effect = nullptr, Node* control = nullptr) { 78 if (!effect) { 79 effect = effect_; 80 } 81 if (!control) { 82 control = control_; 83 } 84 return effect_ = graph()->NewNode(simplified()->StoreField(access), 85 allocation, value, effect, control); 86 } 87 88 Node* Load(const FieldAccess& access, Node* from, Node* effect = nullptr, 89 Node* control = nullptr) { 90 if (!effect) { 91 effect = effect_; 92 } 93 if (!control) { 94 control = control_; 95 } 96 return graph()->NewNode(simplified()->LoadField(access), from, effect, 97 control); 98 } 99 100 Node* Return(Node* value, Node* effect = nullptr, Node* control = nullptr) { 101 if (!effect) { 102 effect = effect_; 103 } 104 if (!control) { 105 control = control_; 106 } 107 return control_ = 108 graph()->NewNode(common()->Return(), value, effect, control); 109 } 110 111 void EndGraph() { 112 for (Edge edge : graph()->end()->input_edges()) { 113 if (NodeProperties::IsControlEdge(edge)) { 114 edge.UpdateTo(control_); 115 } 116 } 117 } 118 119 Node* Branch() { 120 return control_ = 121 graph()->NewNode(common()->Branch(), Constant(0), control_); 122 } 123 124 Node* IfTrue() { 125 return control_ = graph()->NewNode(common()->IfTrue(), control_); 126 } 127 128 Node* IfFalse() { return graph()->NewNode(common()->IfFalse(), control_); } 129 130 Node* Merge2(Node* control1, Node* control2) { 131 return control_ = graph()->NewNode(common()->Merge(2), control1, control2); 132 } 133 134 FieldAccess AccessAtIndex(int offset) { 135 FieldAccess access = {kTaggedBase, offset, MaybeHandle<Name>(), Type::Any(), 136 MachineType::AnyTagged()}; 137 return access; 138 } 139 140 // ---------------------------------Assertion Helper-------------------------- 141 142 void ExpectReplacement(Node* node, Node* rep) { 143 EXPECT_EQ(rep, escape_analysis()->GetReplacement(node)); 144 } 145 146 void ExpectReplacementPhi(Node* node, Node* left, Node* right) { 147 Node* rep = escape_analysis()->GetReplacement(node); 148 ASSERT_NE(nullptr, rep); 149 ASSERT_EQ(IrOpcode::kPhi, rep->opcode()); 150 EXPECT_EQ(left, NodeProperties::GetValueInput(rep, 0)); 151 EXPECT_EQ(right, NodeProperties::GetValueInput(rep, 1)); 152 } 153 154 void ExpectVirtual(Node* node) { 155 EXPECT_TRUE(node->opcode() == IrOpcode::kAllocate || 156 node->opcode() == IrOpcode::kFinishRegion); 157 EXPECT_TRUE(escape_analysis()->IsVirtual(node)); 158 } 159 160 void ExpectEscaped(Node* node) { 161 EXPECT_TRUE(node->opcode() == IrOpcode::kAllocate || 162 node->opcode() == IrOpcode::kFinishRegion); 163 EXPECT_TRUE(escape_analysis()->IsEscaped(node)); 164 } 165 166 SimplifiedOperatorBuilder* simplified() { return &simplified_; } 167 168 Node* effect() { return effect_; } 169 170 private: 171 SimplifiedOperatorBuilder simplified_; 172 JSGraph jsgraph_; 173 EscapeAnalysis escape_analysis_; 174 175 Node* effect_; 176 Node* control_; 177 }; 178 179 180 // ----------------------------------------------------------------------------- 181 // Test cases. 182 183 184 TEST_F(EscapeAnalysisTest, StraightNonEscape) { 185 Node* object1 = Constant(1); 186 BeginRegion(); 187 Node* allocation = Allocate(Constant(kPointerSize)); 188 Store(AccessAtIndex(0), allocation, object1); 189 Node* finish = FinishRegion(allocation); 190 Node* load = Load(AccessAtIndex(0), finish); 191 Node* result = Return(load); 192 EndGraph(); 193 194 Analysis(); 195 196 ExpectVirtual(allocation); 197 ExpectReplacement(load, object1); 198 199 Transformation(); 200 201 ASSERT_EQ(object1, NodeProperties::GetValueInput(result, 0)); 202 } 203 204 205 TEST_F(EscapeAnalysisTest, StraightEscape) { 206 Node* object1 = Constant(1); 207 BeginRegion(); 208 Node* allocation = Allocate(Constant(kPointerSize)); 209 Store(AccessAtIndex(0), allocation, object1); 210 Node* finish = FinishRegion(allocation); 211 Node* load = Load(AccessAtIndex(0), finish); 212 Node* result = Return(allocation); 213 EndGraph(); 214 graph()->end()->AppendInput(zone(), load); 215 216 Analysis(); 217 218 ExpectEscaped(allocation); 219 ExpectReplacement(load, object1); 220 221 Transformation(); 222 223 ASSERT_EQ(allocation, NodeProperties::GetValueInput(result, 0)); 224 } 225 226 227 TEST_F(EscapeAnalysisTest, StoreLoadEscape) { 228 Node* object1 = Constant(1); 229 230 BeginRegion(); 231 Node* allocation1 = Allocate(Constant(kPointerSize)); 232 Store(AccessAtIndex(0), allocation1, object1); 233 Node* finish1 = FinishRegion(allocation1); 234 235 BeginRegion(); 236 Node* allocation2 = Allocate(Constant(kPointerSize)); 237 Store(AccessAtIndex(0), allocation2, finish1); 238 Node* finish2 = FinishRegion(allocation2); 239 240 Node* load = Load(AccessAtIndex(0), finish2); 241 Node* result = Return(load); 242 EndGraph(); 243 Analysis(); 244 245 ExpectEscaped(allocation1); 246 ExpectVirtual(allocation2); 247 ExpectReplacement(load, finish1); 248 249 Transformation(); 250 251 ASSERT_EQ(finish1, NodeProperties::GetValueInput(result, 0)); 252 } 253 254 255 TEST_F(EscapeAnalysisTest, BranchNonEscape) { 256 Node* object1 = Constant(1); 257 Node* object2 = Constant(2); 258 BeginRegion(); 259 Node* allocation = Allocate(Constant(kPointerSize)); 260 Store(AccessAtIndex(0), allocation, object1); 261 Node* finish = FinishRegion(allocation); 262 Branch(); 263 Node* ifFalse = IfFalse(); 264 Node* ifTrue = IfTrue(); 265 Node* effect1 = Store(AccessAtIndex(0), allocation, object1, finish, ifFalse); 266 Node* effect2 = Store(AccessAtIndex(0), allocation, object2, finish, ifTrue); 267 Node* merge = Merge2(ifFalse, ifTrue); 268 Node* phi = graph()->NewNode(common()->EffectPhi(2), effect1, effect2, merge); 269 Node* load = Load(AccessAtIndex(0), finish, phi, merge); 270 Node* result = Return(load, phi); 271 EndGraph(); 272 graph()->end()->AppendInput(zone(), result); 273 274 Analysis(); 275 276 ExpectVirtual(allocation); 277 ExpectReplacementPhi(load, object1, object2); 278 Node* replacement_phi = escape_analysis()->GetReplacement(load); 279 280 Transformation(); 281 282 ASSERT_EQ(replacement_phi, NodeProperties::GetValueInput(result, 0)); 283 } 284 285 286 TEST_F(EscapeAnalysisTest, DanglingLoadOrder) { 287 Node* object1 = Constant(1); 288 Node* object2 = Constant(2); 289 Node* allocation = Allocate(Constant(kPointerSize)); 290 Node* store1 = Store(AccessAtIndex(0), allocation, object1); 291 Node* load1 = Load(AccessAtIndex(0), allocation); 292 Node* store2 = Store(AccessAtIndex(0), allocation, object2); 293 Node* load2 = Load(AccessAtIndex(0), allocation, store1); 294 Node* result = Return(load2); 295 EndGraph(); 296 graph()->end()->AppendInput(zone(), store2); 297 graph()->end()->AppendInput(zone(), load1); 298 299 Analysis(); 300 301 ExpectVirtual(allocation); 302 ExpectReplacement(load1, object1); 303 ExpectReplacement(load2, object1); 304 305 Transformation(); 306 307 ASSERT_EQ(object1, NodeProperties::GetValueInput(result, 0)); 308 } 309 310 311 TEST_F(EscapeAnalysisTest, DeoptReplacement) { 312 Node* object1 = Constant(1); 313 BeginRegion(); 314 Node* allocation = Allocate(Constant(kPointerSize)); 315 Store(AccessAtIndex(0), allocation, object1); 316 Node* finish = FinishRegion(allocation); 317 Node* effect1 = Store(AccessAtIndex(0), allocation, object1, finish); 318 Branch(); 319 Node* ifFalse = IfFalse(); 320 Node* state_values1 = graph()->NewNode(common()->StateValues(1), finish); 321 Node* state_values2 = graph()->NewNode(common()->StateValues(0)); 322 Node* state_values3 = graph()->NewNode(common()->StateValues(0)); 323 Node* frame_state = graph()->NewNode( 324 common()->FrameState(BailoutId::None(), OutputFrameStateCombine::Ignore(), 325 nullptr), 326 state_values1, state_values2, state_values3, UndefinedConstant(), 327 graph()->start(), graph()->start()); 328 Node* deopt = graph()->NewNode(common()->Deoptimize(DeoptimizeKind::kEager), 329 frame_state, effect1, ifFalse); 330 Node* ifTrue = IfTrue(); 331 Node* load = Load(AccessAtIndex(0), finish, effect1, ifTrue); 332 Node* result = Return(load, effect1, ifTrue); 333 EndGraph(); 334 graph()->end()->AppendInput(zone(), deopt); 335 Analysis(); 336 337 ExpectVirtual(allocation); 338 ExpectReplacement(load, object1); 339 340 Transformation(); 341 342 ASSERT_EQ(object1, NodeProperties::GetValueInput(result, 0)); 343 Node* object_state = NodeProperties::GetValueInput(state_values1, 0); 344 ASSERT_EQ(object_state->opcode(), IrOpcode::kObjectState); 345 ASSERT_EQ(1, object_state->op()->ValueInputCount()); 346 ASSERT_EQ(object1, NodeProperties::GetValueInput(object_state, 0)); 347 } 348 349 350 TEST_F(EscapeAnalysisTest, DeoptReplacementIdentity) { 351 Node* object1 = Constant(1); 352 BeginRegion(); 353 Node* allocation = Allocate(Constant(kPointerSize * 2)); 354 Store(AccessAtIndex(0), allocation, object1); 355 Store(AccessAtIndex(kPointerSize), allocation, allocation); 356 Node* finish = FinishRegion(allocation); 357 Node* effect1 = Store(AccessAtIndex(0), allocation, object1, finish); 358 Branch(); 359 Node* ifFalse = IfFalse(); 360 Node* state_values1 = graph()->NewNode(common()->StateValues(1), finish); 361 Node* state_values2 = graph()->NewNode(common()->StateValues(1), finish); 362 Node* state_values3 = graph()->NewNode(common()->StateValues(0)); 363 Node* frame_state = graph()->NewNode( 364 common()->FrameState(BailoutId::None(), OutputFrameStateCombine::Ignore(), 365 nullptr), 366 state_values1, state_values2, state_values3, UndefinedConstant(), 367 graph()->start(), graph()->start()); 368 Node* deopt = graph()->NewNode(common()->Deoptimize(DeoptimizeKind::kEager), 369 frame_state, effect1, ifFalse); 370 Node* ifTrue = IfTrue(); 371 Node* load = Load(AccessAtIndex(0), finish, effect1, ifTrue); 372 Node* result = Return(load, effect1, ifTrue); 373 EndGraph(); 374 graph()->end()->AppendInput(zone(), deopt); 375 Analysis(); 376 377 ExpectVirtual(allocation); 378 ExpectReplacement(load, object1); 379 380 Transformation(); 381 382 ASSERT_EQ(object1, NodeProperties::GetValueInput(result, 0)); 383 384 Node* object_state = NodeProperties::GetValueInput(state_values1, 0); 385 ASSERT_EQ(object_state->opcode(), IrOpcode::kObjectState); 386 ASSERT_EQ(2, object_state->op()->ValueInputCount()); 387 ASSERT_EQ(object1, NodeProperties::GetValueInput(object_state, 0)); 388 ASSERT_EQ(object_state, NodeProperties::GetValueInput(object_state, 1)); 389 390 Node* object_state2 = NodeProperties::GetValueInput(state_values1, 0); 391 ASSERT_EQ(object_state, object_state2); 392 } 393 394 } // namespace compiler 395 } // namespace internal 396 } // namespace v8 397
