src/v8/test/cctest/compiler/test-gap-resolver.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/gap-resolver.h"
   6
   7 #include "src/base/utils/random-number-generator.h"
   8 #include "test/cctest/cctest.h"
   9
  10 using namespace v8::internal;
  11 using namespace v8::internal::compiler;
  12
  13 // The state of our move interpreter is the mapping of operands to values. Note
  14 // that the actual values don't really matter, all we care about is equality.
  15 class InterpreterState {
  16  public:
  17   typedef std::vector<MoveOperands> Moves;
  18
  19   void ExecuteInParallel(Moves moves) {
  20     InterpreterState copy(*this);
  21     for (Moves::iterator it = moves.begin(); it != moves.end(); ++it) {
  22       if (!it->IsRedundant()) write(it->destination(), copy.read(it->source()));
  23     }
  24   }
  25
  26   bool operator==(const InterpreterState& other) const {
  27     return values_ == other.values_;
  28   }
  29
  30   bool operator!=(const InterpreterState& other) const {
  31     return values_ != other.values_;
  32   }
  33
  34  private:
  35   // Internally, the state is a normalized permutation of (kind,index) pairs.
  36   typedef std::pair<InstructionOperand::Kind, int> Key;
  37   typedef Key Value;
  38   typedef std::map<Key, Value> OperandMap;
  39
  40   Value read(const InstructionOperand* op) const {
  41     OperandMap::const_iterator it = values_.find(KeyFor(op));
  42     return (it == values_.end()) ? ValueFor(op) : it->second;
  43   }
  44
  45   void write(const InstructionOperand* op, Value v) {
  46     if (v == ValueFor(op)) {
  47       values_.erase(KeyFor(op));
  48     } else {
  49       values_[KeyFor(op)] = v;
  50     }
  51   }
  52
  53   static Key KeyFor(const InstructionOperand* op) {
  54     return Key(op->kind(), op->index());
  55   }
  56
  57   static Value ValueFor(const InstructionOperand* op) {
  58     return Value(op->kind(), op->index());
  59   }
  60
  61   friend OStream& operator<<(OStream& os, const InterpreterState& is) {
  62     for (OperandMap::const_iterator it = is.values_.begin();
  63          it != is.values_.end(); ++it) {
  64       if (it != is.values_.begin()) os << " ";
  65       InstructionOperand source(it->first.first, it->first.second);
  66       InstructionOperand destination(it->second.first, it->second.second);
  67       os << MoveOperands(&source, &destination);
  68     }
  69     return os;
  70   }
  71
  72   OperandMap values_;
  73 };
  74
  75
  76 // An abstract interpreter for moves, swaps and parallel moves.
  77 class MoveInterpreter : public GapResolver::Assembler {
  78  public:
  79   virtual void AssembleMove(InstructionOperand* source,
  80                             InstructionOperand* destination) V8_OVERRIDE {
  81     InterpreterState::Moves moves;
  82     moves.push_back(MoveOperands(source, destination));
  83     state_.ExecuteInParallel(moves);
  84   }
  85
  86   virtual void AssembleSwap(InstructionOperand* source,
  87                             InstructionOperand* destination) V8_OVERRIDE {
  88     InterpreterState::Moves moves;
  89     moves.push_back(MoveOperands(source, destination));
  90     moves.push_back(MoveOperands(destination, source));
  91     state_.ExecuteInParallel(moves);
  92   }
  93
  94   void AssembleParallelMove(const ParallelMove* pm) {
  95     InterpreterState::Moves moves(pm->move_operands()->begin(),
  96                                   pm->move_operands()->end());
  97     state_.ExecuteInParallel(moves);
  98   }
  99
 100   InterpreterState state() const { return state_; }
 101
 102  private:
 103   InterpreterState state_;
 104 };
 105
 106
 107 class ParallelMoveCreator : public HandleAndZoneScope {
 108  public:
 109   ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {}
 110
 111   ParallelMove* Create(int size) {
 112     ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
 113     std::set<InstructionOperand*, InstructionOperandComparator> seen;
 114     for (int i = 0; i < size; ++i) {
 115       MoveOperands mo(CreateRandomOperand(), CreateRandomOperand());
 116       if (!mo.IsRedundant() && seen.find(mo.destination()) == seen.end()) {
 117         parallel_move->AddMove(mo.source(), mo.destination(), main_zone());
 118         seen.insert(mo.destination());
 119       }
 120     }
 121     return parallel_move;
 122   }
 123
 124  private:
 125   struct InstructionOperandComparator {
 126     bool operator()(const InstructionOperand* x,
 127                     const InstructionOperand* y) const {
 128       return (x->kind() < y->kind()) ||
 129              (x->kind() == y->kind() && x->index() < y->index());
 130     }
 131   };
 132
 133   InstructionOperand* CreateRandomOperand() {
 134     int index = rng_->NextInt(6);
 135     switch (rng_->NextInt(5)) {
 136       case 0:
 137         return ConstantOperand::Create(index, main_zone());
 138       case 1:
 139         return StackSlotOperand::Create(index, main_zone());
 140       case 2:
 141         return DoubleStackSlotOperand::Create(index, main_zone());
 142       case 3:
 143         return RegisterOperand::Create(index, main_zone());
 144       case 4:
 145         return DoubleRegisterOperand::Create(index, main_zone());
 146     }
 147     UNREACHABLE();
 148     return NULL;
 149   }
 150
 151  private:
 152   v8::base::RandomNumberGenerator* rng_;
 153 };
 154
 155
 156 TEST(FuzzResolver) {
 157   ParallelMoveCreator pmc;
 158   for (int size = 0; size < 20; ++size) {
 159     for (int repeat = 0; repeat < 50; ++repeat) {
 160       ParallelMove* pm = pmc.Create(size);
 161
 162       // Note: The gap resolver modifies the ParallelMove, so interpret first.
 163       MoveInterpreter mi1;
 164       mi1.AssembleParallelMove(pm);
 165
 166       MoveInterpreter mi2;
 167       GapResolver resolver(&mi2);
 168       resolver.Resolve(pm);
 169
 170       CHECK(mi1.state() == mi2.state());
 171     }
 172   }
 173 }