Home | History | Annotate | Download | only in compiler 
      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) 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) 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 }
    174