deps/v8/test/unittests/compiler/liveness-analyzer-unittest.cc

   1 // Copyright 2014 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/js-graph.h"
   6 #include "src/compiler/linkage.h"
   7 #include "src/compiler/liveness-analyzer.h"
   8 #include "src/compiler/node-matchers.h"
   9 #include "src/compiler/state-values-utils.h"
  10 #include "test/unittests/compiler/graph-unittest.h"
  11 #include "test/unittests/compiler/node-test-utils.h"
  12
  13 using testing::MakeMatcher;
  14 using testing::MatcherInterface;
  15 using testing::MatchResultListener;
  16 using testing::StringMatchResultListener;
  17
  18 namespace v8 {
  19 namespace internal {
  20 namespace compiler {
  21
  22 class LivenessAnalysisTest : public GraphTest {
  23  public:
  24   explicit LivenessAnalysisTest(int locals_count = 4)
  25       : locals_count_(locals_count),
  26         machine_(zone(), kRepWord32),
  27         javascript_(zone()),
  28         jsgraph_(isolate(), graph(), common(), &javascript_, &machine_),
  29         analyzer_(locals_count, zone()),
  30         empty_values_(graph()->NewNode(common()->StateValues(0), 0, nullptr)),
  31         next_checkpoint_id_(0),
  32         current_block_(nullptr) {}
  33
  34
  35  protected:
  36   JSGraph* jsgraph() { return &jsgraph_; }
  37
  38   LivenessAnalyzer* analyzer() { return &analyzer_; }
  39   void Run() {
  40     StateValuesCache cache(jsgraph());
  41     NonLiveFrameStateSlotReplacer replacer(&cache,
  42                                            jsgraph()->UndefinedConstant(),
  43                                            analyzer()->local_count(), zone());
  44     analyzer()->Run(&replacer);
  45   }
  46
  47   Node* Checkpoint() {
  48     int ast_num = next_checkpoint_id_++;
  49     int first_const = intconst_from_bailout_id(ast_num, locals_count_);
  50
  51     const Operator* locals_op = common()->StateValues(locals_count_);
  52
  53     ZoneVector<Node*> local_inputs(locals_count_, nullptr, zone());
  54     for (int i = 0; i < locals_count_; i++) {
  55       local_inputs[i] = jsgraph()->Int32Constant(i + first_const);
  56     }
  57     Node* locals =
  58         graph()->NewNode(locals_op, locals_count_, &local_inputs.front());
  59
  60     const Operator* op = common()->FrameState(
  61         JS_FRAME, BailoutId(ast_num), OutputFrameStateCombine::Ignore());
  62     Node* result = graph()->NewNode(op, empty_values_, locals, empty_values_,
  63                                     jsgraph()->UndefinedConstant(),
  64                                     jsgraph()->UndefinedConstant());
  65
  66     current_block_->Checkpoint(result);
  67     return result;
  68   }
  69
  70   void Bind(int var) { current_block()->Bind(var); }
  71   void Lookup(int var) { current_block()->Lookup(var); }
  72
  73   class CheckpointMatcher : public MatcherInterface<Node*> {
  74    public:
  75     explicit CheckpointMatcher(const char* liveness, Node* empty_values,
  76                                int locals_count, Node* replacement)
  77         : liveness_(liveness),
  78           empty_values_(empty_values),
  79           locals_count_(locals_count),
  80           replacement_(replacement) {}
  81
  82     void DescribeTo(std::ostream* os) const OVERRIDE {
  83       *os << "is a frame state with '" << liveness_
  84           << "' liveness, empty "
  85              "parameters and empty expression stack";
  86     }
  87
  88     bool MatchAndExplain(Node* frame_state,
  89                          MatchResultListener* listener) const OVERRIDE {
  90       if (frame_state == NULL) {
  91         *listener << "which is NULL";
  92         return false;
  93       }
  94       DCHECK(frame_state->opcode() == IrOpcode::kFrameState);
  95
  96       FrameStateCallInfo state_info =
  97           OpParameter<FrameStateCallInfo>(frame_state);
  98       int ast_num = state_info.bailout_id().ToInt();
  99       int first_const = intconst_from_bailout_id(ast_num, locals_count_);
 100
 101       if (empty_values_ != frame_state->InputAt(0)) {
 102         *listener << "whose parameters are " << frame_state->InputAt(0)
 103                   << " but should have been " << empty_values_ << " (empty)";
 104         return false;
 105       }
 106       if (empty_values_ != frame_state->InputAt(2)) {
 107         *listener << "whose expression stack is " << frame_state->InputAt(2)
 108                   << " but should have been " << empty_values_ << " (empty)";
 109         return false;
 110       }
 111       StateValuesAccess locals(frame_state->InputAt(1));
 112       if (locals_count_ != static_cast<int>(locals.size())) {
 113         *listener << "whose number of locals is " << locals.size()
 114                   << " but should have been " << locals_count_;
 115         return false;
 116       }
 117       int i = 0;
 118       for (StateValuesAccess::TypedNode value : locals) {
 119         if (liveness_[i] == 'L') {
 120           StringMatchResultListener value_listener;
 121           if (value.node == replacement_) {
 122             *listener << "whose local #" << i << " was " << value.node->opcode()
 123                       << " but should have been 'undefined'";
 124             return false;
 125           } else if (!IsInt32Constant(first_const + i)
 126                           .MatchAndExplain(value.node, &value_listener)) {
 127             *listener << "whose local #" << i << " does not match";
 128             if (value_listener.str() != "") {
 129               *listener << ", " << value_listener.str();
 130             }
 131             return false;
 132           }
 133         } else if (liveness_[i] == '.') {
 134           if (value.node != replacement_) {
 135             *listener << "whose local #" << i << " is " << value.node
 136                       << " but should have been " << replacement_
 137                       << " (undefined)";
 138             return false;
 139           }
 140         } else {
 141           UNREACHABLE();
 142         }
 143         i++;
 144       }
 145       return true;
 146     }
 147
 148    private:
 149     const char* liveness_;
 150     Node* empty_values_;
 151     int locals_count_;
 152     Node* replacement_;
 153   };
 154
 155   Matcher<Node*> IsCheckpointModuloLiveness(const char* liveness) {
 156     return MakeMatcher(new CheckpointMatcher(liveness, empty_values_,
 157                                              locals_count_,
 158                                              jsgraph()->UndefinedConstant()));
 159   }
 160
 161   LivenessAnalyzerBlock* current_block() { return current_block_; }
 162   void set_current_block(LivenessAnalyzerBlock* block) {
 163     current_block_ = block;
 164   }
 165
 166  private:
 167   static int intconst_from_bailout_id(int ast_num, int locals_count) {
 168     return (locals_count + 1) * ast_num + 1;
 169   }
 170
 171   int locals_count_;
 172   MachineOperatorBuilder machine_;
 173   JSOperatorBuilder javascript_;
 174   JSGraph jsgraph_;
 175   LivenessAnalyzer analyzer_;
 176   Node* empty_values_;
 177   int next_checkpoint_id_;
 178   LivenessAnalyzerBlock* current_block_;
 179 };
 180
 181
 182 TEST_F(LivenessAnalysisTest, EmptyBlock) {
 183   set_current_block(analyzer()->NewBlock());
 184
 185   Node* c1 = Checkpoint();
 186
 187   Run();
 188
 189   // Nothing is live.
 190   EXPECT_THAT(c1, IsCheckpointModuloLiveness("...."));
 191 }
 192
 193
 194 TEST_F(LivenessAnalysisTest, SimpleLookup) {
 195   set_current_block(analyzer()->NewBlock());
 196
 197   Node* c1 = Checkpoint();
 198   Lookup(1);
 199   Node* c2 = Checkpoint();
 200
 201   Run();
 202
 203   EXPECT_THAT(c1, IsCheckpointModuloLiveness(".L.."));
 204   EXPECT_THAT(c2, IsCheckpointModuloLiveness("...."));
 205 }
 206
 207
 208 TEST_F(LivenessAnalysisTest, DiamondLookups) {
 209   // Start block.
 210   LivenessAnalyzerBlock* start = analyzer()->NewBlock();
 211   set_current_block(start);
 212   Node* c1_start = Checkpoint();
 213
 214   // First branch.
 215   LivenessAnalyzerBlock* b1 = analyzer()->NewBlock(start);
 216   set_current_block(b1);
 217
 218   Node* c1_b1 = Checkpoint();
 219   Lookup(1);
 220   Node* c2_b1 = Checkpoint();
 221   Lookup(3);
 222   Node* c3_b1 = Checkpoint();
 223
 224   // Second branch.
 225   LivenessAnalyzerBlock* b2 = analyzer()->NewBlock(start);
 226   set_current_block(b2);
 227
 228   Node* c1_b2 = Checkpoint();
 229   Lookup(3);
 230   Node* c2_b2 = Checkpoint();
 231   Lookup(2);
 232   Node* c3_b2 = Checkpoint();
 233
 234   // Merge block.
 235   LivenessAnalyzerBlock* m = analyzer()->NewBlock(b1);
 236   m->AddPredecessor(b2);
 237   set_current_block(m);
 238   Node* c1_m = Checkpoint();
 239   Lookup(0);
 240   Node* c2_m = Checkpoint();
 241
 242   Run();
 243
 244   EXPECT_THAT(c1_start, IsCheckpointModuloLiveness("LLLL"));
 245
 246   EXPECT_THAT(c1_b1, IsCheckpointModuloLiveness("LL.L"));
 247   EXPECT_THAT(c2_b1, IsCheckpointModuloLiveness("L..L"));
 248   EXPECT_THAT(c3_b1, IsCheckpointModuloLiveness("L..."));
 249
 250   EXPECT_THAT(c1_b2, IsCheckpointModuloLiveness("L.LL"));
 251   EXPECT_THAT(c2_b2, IsCheckpointModuloLiveness("L.L."));
 252   EXPECT_THAT(c3_b2, IsCheckpointModuloLiveness("L..."));
 253
 254   EXPECT_THAT(c1_m, IsCheckpointModuloLiveness("L..."));
 255   EXPECT_THAT(c2_m, IsCheckpointModuloLiveness("...."));
 256 }
 257
 258
 259 TEST_F(LivenessAnalysisTest, DiamondLookupsAndBinds) {
 260   // Start block.
 261   LivenessAnalyzerBlock* start = analyzer()->NewBlock();
 262   set_current_block(start);
 263   Node* c1_start = Checkpoint();
 264   Bind(0);
 265   Node* c2_start = Checkpoint();
 266
 267   // First branch.
 268   LivenessAnalyzerBlock* b1 = analyzer()->NewBlock(start);
 269   set_current_block(b1);
 270
 271   Node* c1_b1 = Checkpoint();
 272   Bind(2);
 273   Bind(1);
 274   Node* c2_b1 = Checkpoint();
 275   Bind(3);
 276   Node* c3_b1 = Checkpoint();
 277
 278   // Second branch.
 279   LivenessAnalyzerBlock* b2 = analyzer()->NewBlock(start);
 280   set_current_block(b2);
 281
 282   Node* c1_b2 = Checkpoint();
 283   Lookup(2);
 284   Node* c2_b2 = Checkpoint();
 285   Bind(2);
 286   Bind(3);
 287   Node* c3_b2 = Checkpoint();
 288
 289   // Merge block.
 290   LivenessAnalyzerBlock* m = analyzer()->NewBlock(b1);
 291   m->AddPredecessor(b2);
 292   set_current_block(m);
 293   Node* c1_m = Checkpoint();
 294   Lookup(0);
 295   Lookup(1);
 296   Lookup(2);
 297   Lookup(3);
 298   Node* c2_m = Checkpoint();
 299
 300   Run();
 301
 302   EXPECT_THAT(c1_start, IsCheckpointModuloLiveness(".LL."));
 303   EXPECT_THAT(c2_start, IsCheckpointModuloLiveness("LLL."));
 304
 305   EXPECT_THAT(c1_b1, IsCheckpointModuloLiveness("L..."));
 306   EXPECT_THAT(c2_b1, IsCheckpointModuloLiveness("LLL."));
 307   EXPECT_THAT(c3_b1, IsCheckpointModuloLiveness("LLLL"));
 308
 309   EXPECT_THAT(c1_b2, IsCheckpointModuloLiveness("LLL."));
 310   EXPECT_THAT(c2_b2, IsCheckpointModuloLiveness("LL.."));
 311   EXPECT_THAT(c3_b2, IsCheckpointModuloLiveness("LLLL"));
 312
 313   EXPECT_THAT(c1_m, IsCheckpointModuloLiveness("LLLL"));
 314   EXPECT_THAT(c2_m, IsCheckpointModuloLiveness("...."));
 315 }
 316
 317
 318 TEST_F(LivenessAnalysisTest, SimpleLoop) {
 319   // Start block.
 320   LivenessAnalyzerBlock* start = analyzer()->NewBlock();
 321   set_current_block(start);
 322   Node* c1_start = Checkpoint();
 323   Bind(0);
 324   Bind(1);
 325   Bind(2);
 326   Bind(3);
 327   Node* c2_start = Checkpoint();
 328
 329   // Loop header block.
 330   LivenessAnalyzerBlock* header = analyzer()->NewBlock(start);
 331   set_current_block(header);
 332   Node* c1_header = Checkpoint();
 333   Lookup(0);
 334   Bind(2);
 335   Node* c2_header = Checkpoint();
 336
 337   // Inside-loop block.
 338   LivenessAnalyzerBlock* in_loop = analyzer()->NewBlock(header);
 339   set_current_block(in_loop);
 340   Node* c1_in_loop = Checkpoint();
 341   Bind(0);
 342   Lookup(3);
 343   Node* c2_in_loop = Checkpoint();
 344
 345   // Add back edge.
 346   header->AddPredecessor(in_loop);
 347
 348   // After-loop block.
 349   LivenessAnalyzerBlock* end = analyzer()->NewBlock(header);
 350   set_current_block(end);
 351   Node* c1_end = Checkpoint();
 352   Lookup(1);
 353   Lookup(2);
 354   Node* c2_end = Checkpoint();
 355
 356   Run();
 357
 358   EXPECT_THAT(c1_start, IsCheckpointModuloLiveness("...."));
 359   EXPECT_THAT(c2_start, IsCheckpointModuloLiveness("LL.L"));
 360
 361   EXPECT_THAT(c1_header, IsCheckpointModuloLiveness("LL.L"));
 362   EXPECT_THAT(c2_header, IsCheckpointModuloLiveness(".LLL"));
 363
 364   EXPECT_THAT(c1_in_loop, IsCheckpointModuloLiveness(".L.L"));
 365   EXPECT_THAT(c2_in_loop, IsCheckpointModuloLiveness("LL.L"));
 366
 367   EXPECT_THAT(c1_end, IsCheckpointModuloLiveness(".LL."));
 368   EXPECT_THAT(c2_end, IsCheckpointModuloLiveness("...."));
 369 }
 370
 371 }  // namespace compiler
 372 }  // namespace internal
 373 }  // namespace v8