| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/compiler/js-graph.h" |
| #include "src/compiler/linkage.h" |
| #include "src/compiler/liveness-analyzer.h" |
| #include "src/compiler/node-matchers.h" |
| #include "src/compiler/state-values-utils.h" |
| #include "test/unittests/compiler/graph-unittest.h" |
| #include "test/unittests/compiler/node-test-utils.h" |
| |
| using testing::MakeMatcher; |
| using testing::MatcherInterface; |
| using testing::MatchResultListener; |
| using testing::StringMatchResultListener; |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| class LivenessAnalysisTest : public GraphTest { |
| public: |
| explicit LivenessAnalysisTest(int locals_count = 4) |
| : locals_count_(locals_count), |
| machine_(zone(), MachineRepresentation::kWord32), |
| javascript_(zone()), |
| jsgraph_(isolate(), graph(), common(), &javascript_, nullptr, |
| &machine_), |
| analyzer_(locals_count, zone()), |
| empty_values_(graph()->NewNode(common()->StateValues(0), 0, nullptr)), |
| next_checkpoint_id_(0), |
| current_block_(nullptr) {} |
| |
| |
| protected: |
| JSGraph* jsgraph() { return &jsgraph_; } |
| |
| LivenessAnalyzer* analyzer() { return &analyzer_; } |
| void Run() { |
| StateValuesCache cache(jsgraph()); |
| NonLiveFrameStateSlotReplacer replacer(&cache, |
| jsgraph()->UndefinedConstant(), |
| analyzer()->local_count(), zone()); |
| analyzer()->Run(&replacer); |
| } |
| |
| Node* Checkpoint() { |
| int ast_num = next_checkpoint_id_++; |
| int first_const = intconst_from_bailout_id(ast_num, locals_count_); |
| |
| const Operator* locals_op = common()->StateValues(locals_count_); |
| |
| ZoneVector<Node*> local_inputs(locals_count_, nullptr, zone()); |
| for (int i = 0; i < locals_count_; i++) { |
| local_inputs[i] = jsgraph()->Int32Constant(i + first_const); |
| } |
| Node* locals = |
| graph()->NewNode(locals_op, locals_count_, &local_inputs.front()); |
| |
| const FrameStateFunctionInfo* state_info = |
| common()->CreateFrameStateFunctionInfo( |
| FrameStateType::kJavaScriptFunction, 0, locals_count_, |
| Handle<SharedFunctionInfo>(), CALL_MAINTAINS_NATIVE_CONTEXT); |
| |
| const Operator* op = common()->FrameState( |
| BailoutId(ast_num), OutputFrameStateCombine::Ignore(), state_info); |
| Node* result = |
| graph()->NewNode(op, empty_values_, locals, empty_values_, |
| jsgraph()->UndefinedConstant(), |
| jsgraph()->UndefinedConstant(), graph()->start()); |
| |
| current_block_->Checkpoint(result); |
| return result; |
| } |
| |
| void Bind(int var) { current_block()->Bind(var); } |
| void Lookup(int var) { current_block()->Lookup(var); } |
| |
| class CheckpointMatcher : public MatcherInterface<Node*> { |
| public: |
| explicit CheckpointMatcher(const char* liveness, Node* empty_values, |
| int locals_count, Node* replacement) |
| : liveness_(liveness), |
| empty_values_(empty_values), |
| locals_count_(locals_count), |
| replacement_(replacement) {} |
| |
| void DescribeTo(std::ostream* os) const override { |
| *os << "is a frame state with '" << liveness_ |
| << "' liveness, empty " |
| "parameters and empty expression stack"; |
| } |
| |
| bool MatchAndExplain(Node* frame_state, |
| MatchResultListener* listener) const override { |
| if (frame_state == NULL) { |
| *listener << "which is NULL"; |
| return false; |
| } |
| DCHECK(frame_state->opcode() == IrOpcode::kFrameState); |
| |
| FrameStateInfo state_info = OpParameter<FrameStateInfo>(frame_state); |
| int ast_num = state_info.bailout_id().ToInt(); |
| int first_const = intconst_from_bailout_id(ast_num, locals_count_); |
| |
| if (empty_values_ != frame_state->InputAt(0)) { |
| *listener << "whose parameters are " << frame_state->InputAt(0) |
| << " but should have been " << empty_values_ << " (empty)"; |
| return false; |
| } |
| if (empty_values_ != frame_state->InputAt(2)) { |
| *listener << "whose expression stack is " << frame_state->InputAt(2) |
| << " but should have been " << empty_values_ << " (empty)"; |
| return false; |
| } |
| StateValuesAccess locals(frame_state->InputAt(1)); |
| if (locals_count_ != static_cast<int>(locals.size())) { |
| *listener << "whose number of locals is " << locals.size() |
| << " but should have been " << locals_count_; |
| return false; |
| } |
| int i = 0; |
| for (StateValuesAccess::TypedNode value : locals) { |
| if (liveness_[i] == 'L') { |
| StringMatchResultListener value_listener; |
| if (value.node == replacement_) { |
| *listener << "whose local #" << i << " was " << value.node->opcode() |
| << " but should have been 'undefined'"; |
| return false; |
| } else if (!IsInt32Constant(first_const + i) |
| .MatchAndExplain(value.node, &value_listener)) { |
| *listener << "whose local #" << i << " does not match"; |
| if (value_listener.str() != "") { |
| *listener << ", " << value_listener.str(); |
| } |
| return false; |
| } |
| } else if (liveness_[i] == '.') { |
| if (value.node != replacement_) { |
| *listener << "whose local #" << i << " is " << value.node |
| << " but should have been " << replacement_ |
| << " (undefined)"; |
| return false; |
| } |
| } else { |
| UNREACHABLE(); |
| } |
| i++; |
| } |
| return true; |
| } |
| |
| private: |
| const char* liveness_; |
| Node* empty_values_; |
| int locals_count_; |
| Node* replacement_; |
| }; |
| |
| Matcher<Node*> IsCheckpointModuloLiveness(const char* liveness) { |
| return MakeMatcher(new CheckpointMatcher(liveness, empty_values_, |
| locals_count_, |
| jsgraph()->UndefinedConstant())); |
| } |
| |
| LivenessAnalyzerBlock* current_block() { return current_block_; } |
| void set_current_block(LivenessAnalyzerBlock* block) { |
| current_block_ = block; |
| } |
| |
| private: |
| static int intconst_from_bailout_id(int ast_num, int locals_count) { |
| return (locals_count + 1) * ast_num + 1; |
| } |
| |
| int locals_count_; |
| MachineOperatorBuilder machine_; |
| JSOperatorBuilder javascript_; |
| JSGraph jsgraph_; |
| LivenessAnalyzer analyzer_; |
| Node* empty_values_; |
| int next_checkpoint_id_; |
| LivenessAnalyzerBlock* current_block_; |
| }; |
| |
| |
| TEST_F(LivenessAnalysisTest, EmptyBlock) { |
| set_current_block(analyzer()->NewBlock()); |
| |
| Node* c1 = Checkpoint(); |
| |
| Run(); |
| |
| // Nothing is live. |
| EXPECT_THAT(c1, IsCheckpointModuloLiveness("....")); |
| } |
| |
| |
| TEST_F(LivenessAnalysisTest, SimpleLookup) { |
| set_current_block(analyzer()->NewBlock()); |
| |
| Node* c1 = Checkpoint(); |
| Lookup(1); |
| Node* c2 = Checkpoint(); |
| |
| Run(); |
| |
| EXPECT_THAT(c1, IsCheckpointModuloLiveness(".L..")); |
| EXPECT_THAT(c2, IsCheckpointModuloLiveness("....")); |
| } |
| |
| |
| TEST_F(LivenessAnalysisTest, DiamondLookups) { |
| // Start block. |
| LivenessAnalyzerBlock* start = analyzer()->NewBlock(); |
| set_current_block(start); |
| Node* c1_start = Checkpoint(); |
| |
| // First branch. |
| LivenessAnalyzerBlock* b1 = analyzer()->NewBlock(start); |
| set_current_block(b1); |
| |
| Node* c1_b1 = Checkpoint(); |
| Lookup(1); |
| Node* c2_b1 = Checkpoint(); |
| Lookup(3); |
| Node* c3_b1 = Checkpoint(); |
| |
| // Second branch. |
| LivenessAnalyzerBlock* b2 = analyzer()->NewBlock(start); |
| set_current_block(b2); |
| |
| Node* c1_b2 = Checkpoint(); |
| Lookup(3); |
| Node* c2_b2 = Checkpoint(); |
| Lookup(2); |
| Node* c3_b2 = Checkpoint(); |
| |
| // Merge block. |
| LivenessAnalyzerBlock* m = analyzer()->NewBlock(b1); |
| m->AddPredecessor(b2); |
| set_current_block(m); |
| Node* c1_m = Checkpoint(); |
| Lookup(0); |
| Node* c2_m = Checkpoint(); |
| |
| Run(); |
| |
| EXPECT_THAT(c1_start, IsCheckpointModuloLiveness("LLLL")); |
| |
| EXPECT_THAT(c1_b1, IsCheckpointModuloLiveness("LL.L")); |
| EXPECT_THAT(c2_b1, IsCheckpointModuloLiveness("L..L")); |
| EXPECT_THAT(c3_b1, IsCheckpointModuloLiveness("L...")); |
| |
| EXPECT_THAT(c1_b2, IsCheckpointModuloLiveness("L.LL")); |
| EXPECT_THAT(c2_b2, IsCheckpointModuloLiveness("L.L.")); |
| EXPECT_THAT(c3_b2, IsCheckpointModuloLiveness("L...")); |
| |
| EXPECT_THAT(c1_m, IsCheckpointModuloLiveness("L...")); |
| EXPECT_THAT(c2_m, IsCheckpointModuloLiveness("....")); |
| } |
| |
| |
| TEST_F(LivenessAnalysisTest, DiamondLookupsAndBinds) { |
| // Start block. |
| LivenessAnalyzerBlock* start = analyzer()->NewBlock(); |
| set_current_block(start); |
| Node* c1_start = Checkpoint(); |
| Bind(0); |
| Node* c2_start = Checkpoint(); |
| |
| // First branch. |
| LivenessAnalyzerBlock* b1 = analyzer()->NewBlock(start); |
| set_current_block(b1); |
| |
| Node* c1_b1 = Checkpoint(); |
| Bind(2); |
| Bind(1); |
| Node* c2_b1 = Checkpoint(); |
| Bind(3); |
| Node* c3_b1 = Checkpoint(); |
| |
| // Second branch. |
| LivenessAnalyzerBlock* b2 = analyzer()->NewBlock(start); |
| set_current_block(b2); |
| |
| Node* c1_b2 = Checkpoint(); |
| Lookup(2); |
| Node* c2_b2 = Checkpoint(); |
| Bind(2); |
| Bind(3); |
| Node* c3_b2 = Checkpoint(); |
| |
| // Merge block. |
| LivenessAnalyzerBlock* m = analyzer()->NewBlock(b1); |
| m->AddPredecessor(b2); |
| set_current_block(m); |
| Node* c1_m = Checkpoint(); |
| Lookup(0); |
| Lookup(1); |
| Lookup(2); |
| Lookup(3); |
| Node* c2_m = Checkpoint(); |
| |
| Run(); |
| |
| EXPECT_THAT(c1_start, IsCheckpointModuloLiveness(".LL.")); |
| EXPECT_THAT(c2_start, IsCheckpointModuloLiveness("LLL.")); |
| |
| EXPECT_THAT(c1_b1, IsCheckpointModuloLiveness("L...")); |
| EXPECT_THAT(c2_b1, IsCheckpointModuloLiveness("LLL.")); |
| EXPECT_THAT(c3_b1, IsCheckpointModuloLiveness("LLLL")); |
| |
| EXPECT_THAT(c1_b2, IsCheckpointModuloLiveness("LLL.")); |
| EXPECT_THAT(c2_b2, IsCheckpointModuloLiveness("LL..")); |
| EXPECT_THAT(c3_b2, IsCheckpointModuloLiveness("LLLL")); |
| |
| EXPECT_THAT(c1_m, IsCheckpointModuloLiveness("LLLL")); |
| EXPECT_THAT(c2_m, IsCheckpointModuloLiveness("....")); |
| } |
| |
| |
| TEST_F(LivenessAnalysisTest, SimpleLoop) { |
| // Start block. |
| LivenessAnalyzerBlock* start = analyzer()->NewBlock(); |
| set_current_block(start); |
| Node* c1_start = Checkpoint(); |
| Bind(0); |
| Bind(1); |
| Bind(2); |
| Bind(3); |
| Node* c2_start = Checkpoint(); |
| |
| // Loop header block. |
| LivenessAnalyzerBlock* header = analyzer()->NewBlock(start); |
| set_current_block(header); |
| Node* c1_header = Checkpoint(); |
| Lookup(0); |
| Bind(2); |
| Node* c2_header = Checkpoint(); |
| |
| // Inside-loop block. |
| LivenessAnalyzerBlock* in_loop = analyzer()->NewBlock(header); |
| set_current_block(in_loop); |
| Node* c1_in_loop = Checkpoint(); |
| Bind(0); |
| Lookup(3); |
| Node* c2_in_loop = Checkpoint(); |
| |
| // Add back edge. |
| header->AddPredecessor(in_loop); |
| |
| // After-loop block. |
| LivenessAnalyzerBlock* end = analyzer()->NewBlock(header); |
| set_current_block(end); |
| Node* c1_end = Checkpoint(); |
| Lookup(1); |
| Lookup(2); |
| Node* c2_end = Checkpoint(); |
| |
| Run(); |
| |
| EXPECT_THAT(c1_start, IsCheckpointModuloLiveness("....")); |
| EXPECT_THAT(c2_start, IsCheckpointModuloLiveness("LL.L")); |
| |
| EXPECT_THAT(c1_header, IsCheckpointModuloLiveness("LL.L")); |
| EXPECT_THAT(c2_header, IsCheckpointModuloLiveness(".LLL")); |
| |
| EXPECT_THAT(c1_in_loop, IsCheckpointModuloLiveness(".L.L")); |
| EXPECT_THAT(c2_in_loop, IsCheckpointModuloLiveness("LL.L")); |
| |
| EXPECT_THAT(c1_end, IsCheckpointModuloLiveness(".LL.")); |
| EXPECT_THAT(c2_end, IsCheckpointModuloLiveness("....")); |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |