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 namespace v8 {
     11 namespace internal {
     12 namespace compiler {
     13 
     14 // The state of our move interpreter is the mapping of operands to values. Note
     15 // that the actual values don't really matter, all we care about is equality.
     16 class InterpreterState {
     17  public:
     18   void ExecuteInParallel(const ParallelMove* moves) {
     19     InterpreterState copy(*this);
     20     for (const auto m : *moves) {
     21       if (!m->IsRedundant()) write(m->destination(), copy.read(m->source()));
     22     }
     23   }
     24 
     25   bool operator==(const InterpreterState& other) const {
     26     return values_ == other.values_;
     27   }
     28 
     29   bool operator!=(const InterpreterState& other) const {
     30     return values_ != other.values_;
     31   }
     32 
     33  private:
     34   struct Key {
     35     bool is_constant;
     36     bool is_float;
     37     LocationOperand::LocationKind kind;
     38     int index;
     39 
     40     bool operator<(const Key& other) const {
     41       if (this->is_constant != other.is_constant) {
     42         return this->is_constant;
     43       }
     44       if (this->is_float != other.is_float) {
     45         return this->is_float;
     46       }
     47       if (this->kind != other.kind) {
     48         return this->kind < other.kind;
     49       }
     50       return this->index < other.index;
     51     }
     52 
     53     bool operator==(const Key& other) const {
     54       return this->is_constant == other.is_constant &&
     55              this->kind == other.kind && this->index == other.index;
     56     }
     57   };
     58 
     59   // Internally, the state is a normalized permutation of (kind,index) pairs.
     60   typedef Key Value;
     61   typedef std::map<Key, Value> OperandMap;
     62 
     63   Value read(const InstructionOperand& op) const {
     64     OperandMap::const_iterator it = values_.find(KeyFor(op));
     65     return (it == values_.end()) ? ValueFor(op) : it->second;
     66   }
     67 
     68   void write(const InstructionOperand& op, Value v) {
     69     if (v == ValueFor(op)) {
     70       values_.erase(KeyFor(op));
     71     } else {
     72       values_[KeyFor(op)] = v;
     73     }
     74   }
     75 
     76   static Key KeyFor(const InstructionOperand& op) {
     77     bool is_constant = op.IsConstant();
     78     bool is_float = false;
     79     LocationOperand::LocationKind kind;
     80     int index;
     81     if (!is_constant) {
     82       if (op.IsRegister()) {
     83         index = LocationOperand::cast(op).GetRegister().code();
     84       } else if (op.IsDoubleRegister()) {
     85         index = LocationOperand::cast(op).GetDoubleRegister().code();
     86       } else {
     87         index = LocationOperand::cast(op).index();
     88       }
     89       is_float = IsFloatingPoint(LocationOperand::cast(op).representation());
     90       kind = LocationOperand::cast(op).location_kind();
     91     } else {
     92       index = ConstantOperand::cast(op).virtual_register();
     93       kind = LocationOperand::REGISTER;
     94     }
     95     Key key = {is_constant, is_float, kind, index};
     96     return key;
     97   }
     98 
     99   static Value ValueFor(const InstructionOperand& op) { return KeyFor(op); }
    100 
    101   static InstructionOperand FromKey(Key key) {
    102     if (key.is_constant) {
    103       return ConstantOperand(key.index);
    104     }
    105     return AllocatedOperand(
    106         key.kind,
    107         v8::internal::compiler::InstructionSequence::DefaultRepresentation(),
    108         key.index);
    109   }
    110 
    111   friend std::ostream& operator<<(std::ostream& os,
    112                                   const InterpreterState& is) {
    113     for (OperandMap::const_iterator it = is.values_.begin();
    114          it != is.values_.end(); ++it) {
    115       if (it != is.values_.begin()) os << " ";
    116       InstructionOperand source = FromKey(it->first);
    117       InstructionOperand destination = FromKey(it->second);
    118       MoveOperands mo(source, destination);
    119       PrintableMoveOperands pmo = {
    120           RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
    121           &mo};
    122       os << pmo;
    123     }
    124     return os;
    125   }
    126 
    127   OperandMap values_;
    128 };
    129 
    130 
    131 // An abstract interpreter for moves, swaps and parallel moves.
    132 class MoveInterpreter : public GapResolver::Assembler {
    133  public:
    134   explicit MoveInterpreter(Zone* zone) : zone_(zone) {}
    135 
    136   void AssembleMove(InstructionOperand* source,
    137                     InstructionOperand* destination) override {
    138     ParallelMove* moves = new (zone_) ParallelMove(zone_);
    139     moves->AddMove(*source, *destination);
    140     state_.ExecuteInParallel(moves);
    141   }
    142 
    143   void AssembleSwap(InstructionOperand* source,
    144                     InstructionOperand* destination) override {
    145     ParallelMove* moves = new (zone_) ParallelMove(zone_);
    146     moves->AddMove(*source, *destination);
    147     moves->AddMove(*destination, *source);
    148     state_.ExecuteInParallel(moves);
    149   }
    150 
    151   void AssembleParallelMove(const ParallelMove* moves) {
    152     state_.ExecuteInParallel(moves);
    153   }
    154 
    155   InterpreterState state() const { return state_; }
    156 
    157  private:
    158   Zone* const zone_;
    159   InterpreterState state_;
    160 };
    161 
    162 
    163 class ParallelMoveCreator : public HandleAndZoneScope {
    164  public:
    165   ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {}
    166 
    167   ParallelMove* Create(int size) {
    168     ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
    169     std::set<InstructionOperand, CompareOperandModuloType> seen;
    170     for (int i = 0; i < size; ++i) {
    171       MoveOperands mo(CreateRandomOperand(true), CreateRandomOperand(false));
    172       if (!mo.IsRedundant() && seen.find(mo.destination()) == seen.end()) {
    173         parallel_move->AddMove(mo.source(), mo.destination());
    174         seen.insert(mo.destination());
    175       }
    176     }
    177     return parallel_move;
    178   }
    179 
    180  private:
    181   MachineRepresentation RandomRepresentation() {
    182     int index = rng_->NextInt(3);
    183     switch (index) {
    184       case 0:
    185         return MachineRepresentation::kWord32;
    186       case 1:
    187         return MachineRepresentation::kWord64;
    188       case 2:
    189         return MachineRepresentation::kTagged;
    190     }
    191     UNREACHABLE();
    192     return MachineRepresentation::kNone;
    193   }
    194 
    195   MachineRepresentation RandomDoubleRepresentation() {
    196     int index = rng_->NextInt(2);
    197     if (index == 0) return MachineRepresentation::kFloat64;
    198     return MachineRepresentation::kFloat32;
    199   }
    200 
    201   InstructionOperand CreateRandomOperand(bool is_source) {
    202     int index = rng_->NextInt(7);
    203     // destination can't be Constant.
    204     switch (rng_->NextInt(is_source ? 7 : 6)) {
    205       case 0:
    206         return AllocatedOperand(LocationOperand::STACK_SLOT,
    207                                 RandomRepresentation(), index);
    208       case 1:
    209         return AllocatedOperand(LocationOperand::STACK_SLOT,
    210                                 RandomDoubleRepresentation(), index);
    211       case 2:
    212         return AllocatedOperand(LocationOperand::REGISTER,
    213                                 RandomRepresentation(), index);
    214       case 3:
    215         return AllocatedOperand(LocationOperand::REGISTER,
    216                                 RandomDoubleRepresentation(), index);
    217       case 4:
    218         return ExplicitOperand(
    219             LocationOperand::REGISTER, RandomRepresentation(),
    220             RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN)
    221                 ->GetAllocatableGeneralCode(1));
    222       case 5:
    223         return ExplicitOperand(
    224             LocationOperand::STACK_SLOT, RandomRepresentation(),
    225             RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN)
    226                 ->GetAllocatableGeneralCode(index));
    227       case 6:
    228         return ConstantOperand(index);
    229     }
    230     UNREACHABLE();
    231     return InstructionOperand();
    232   }
    233 
    234  private:
    235   v8::base::RandomNumberGenerator* rng_;
    236 };
    237 
    238 
    239 TEST(FuzzResolver) {
    240   ParallelMoveCreator pmc;
    241   for (int size = 0; size < 20; ++size) {
    242     for (int repeat = 0; repeat < 50; ++repeat) {
    243       ParallelMove* pm = pmc.Create(size);
    244 
    245       // Note: The gap resolver modifies the ParallelMove, so interpret first.
    246       MoveInterpreter mi1(pmc.main_zone());
    247       mi1.AssembleParallelMove(pm);
    248 
    249       MoveInterpreter mi2(pmc.main_zone());
    250       GapResolver resolver(&mi2);
    251       resolver.Resolve(pm);
    252 
    253       CHECK(mi1.state() == mi2.state());
    254     }
    255   }
    256 }
    257 
    258 }  // namespace compiler
    259 }  // namespace internal
    260 }  // namespace v8
    261