[turbofan] add some registerallocator unittests

test/unittests/compiler/register-allocator-unittest.cc

Index: test/unittests/compiler/register-allocator-unittest.cc
diff --git a/test/unittests/compiler/register-allocator-unittest.cc b/test/unittests/compiler/register-allocator-unittest.cc
index db457c0d65a19cc00eb9837cf3ae1ae54bd12bf6..61428bab009b6173033251ce214534d00cc989e3 100644
--- a/test/unittests/compiler/register-allocator-unittest.cc
+++ b/test/unittests/compiler/register-allocator-unittest.cc
@@ -14,8 +14,6 @@ namespace compiler {
 
 typedef BasicBlock::RpoNumber Rpo;
 
-namespace {
-
 static const char*
     general_register_names_[RegisterConfiguration::kMaxGeneralRegisters];
 static const char*
@@ -23,7 +21,6 @@ static const char*
 static char register_names_[10 * (RegisterConfiguration::kMaxGeneralRegisters +
                                   RegisterConfiguration::kMaxDoubleRegisters)];
 
-
 static void InitializeRegisterNames() {
   char* loc = register_names_;
   for (int i = 0; i < RegisterConfiguration::kMaxGeneralRegisters; ++i) {
@@ -38,52 +35,107 @@ static void InitializeRegisterNames() {
   }
 }
 
-enum BlockCompletionType { kBlockEnd, kFallThrough, kBranch, kJump };
 
-struct BlockCompletion {
-  BlockCompletionType type_;
-  int vreg_;
-  int offset_0_;
-  int offset_1_;
-};
+class RegisterAllocatorTest : public TestWithZone {
+ public:
+  static const int kDefaultNRegs = 4;
+  static const int kNoValue = kMinInt;
 
-static const int kInvalidJumpOffset = kMinInt;
+  struct VReg {
+    VReg() : value_(kNoValue) {}
+    VReg(PhiInstruction* phi) : value_(phi->virtual_register()) {}  // NOLINT
+    explicit VReg(int value) : value_(value) {}
+    int value_;
+  };
 
-BlockCompletion FallThrough() {
-  BlockCompletion completion = {kFallThrough, -1, 1, kInvalidJumpOffset};
-  return completion;
-}
+  enum TestOperandType {
+    kInvalid,
+    kSameAsFirst,
+    kRegister,
+    kFixedRegister,
+    kSlot,
+    kFixedSlot,
+    kImmediate,
+    kNone
+  };
 
+  struct TestOperand {
+    TestOperand() : type_(kInvalid), vreg_(), value_(kNoValue) {}
+    TestOperand(TestOperandType type, int imm)
+        : type_(type), vreg_(), value_(imm) {}
+    TestOperand(TestOperandType type, VReg vreg, int value = kNoValue)
+        : type_(type), vreg_(vreg), value_(value) {}
 
-BlockCompletion Jump(int offset) {
-  BlockCompletion completion = {kJump, -1, offset, kInvalidJumpOffset};
-  return completion;
-}
+    TestOperandType type_;
+    VReg vreg_;
+    int value_;
+  };
 
+  static TestOperand Same() { return TestOperand(kSameAsFirst, VReg()); }
 
-BlockCompletion Branch(int vreg, int left_offset, int right_offset) {
-  BlockCompletion completion = {kBranch, vreg, left_offset, right_offset};
-  return completion;
-}
+  static TestOperand Reg(VReg vreg, int index = kNoValue) {
+    TestOperandType type = kRegister;
+    if (index != kNoValue) type = kFixedRegister;
+    return TestOperand(type, vreg, index);
+  }
 
-}  // namespace
+  static TestOperand Reg(int index = kNoValue) { return Reg(VReg(), index); }
 
+  static TestOperand Slot(VReg vreg, int index = kNoValue) {
+    TestOperandType type = kSlot;
+    if (index != kNoValue) type = kFixedSlot;
+    return TestOperand(type, vreg, index);
+  }
 
-class RegisterAllocatorTest : public TestWithZone {
- public:
-  static const int kDefaultNRegs = 4;
+  static TestOperand Slot(int index = kNoValue) { return Slot(VReg(), index); }
+
+  static TestOperand Use(VReg vreg) { return TestOperand(kNone, vreg); }
+
+  static TestOperand Use() { return Use(VReg()); }
+
+  enum BlockCompletionType { kBlockEnd, kFallThrough, kBranch, kJump };
+
+  struct BlockCompletion {
+    BlockCompletionType type_;
+    TestOperand op_;
+    int offset_0_;
+    int offset_1_;
+  };
+
+  static BlockCompletion FallThrough() {
+    BlockCompletion completion = {kFallThrough, TestOperand(), 1, kNoValue};
+    return completion;
+  }
+
+  static BlockCompletion Jump(int offset) {
+    BlockCompletion completion = {kJump, TestOperand(), offset, kNoValue};
+    return completion;
+  }
+
+  static BlockCompletion Branch(TestOperand op, int left_offset,
+                                int right_offset) {
+    BlockCompletion completion = {kBranch, op, left_offset, right_offset};
+    return completion;
+  }
+
+  static BlockCompletion Last() {
+    BlockCompletion completion = {kBlockEnd, TestOperand(), kNoValue, kNoValue};
+    return completion;
+  }
 
   RegisterAllocatorTest()
       : num_general_registers_(kDefaultNRegs),
         num_double_registers_(kDefaultNRegs),
         instruction_blocks_(zone()),
+        current_instruction_index_(-1),
         current_block_(nullptr),
-        is_last_block_(false),
         block_returns_(false) {
     InitializeRegisterNames();
   }
 
   void SetNumRegs(int num_general_registers, int num_double_registers) {
+    CHECK(config_.is_empty());
+    CHECK(instructions_.empty());
     CHECK(instruction_blocks_.empty());
     num_general_registers_ = num_general_registers;
     num_double_registers_ = num_double_registers;
@@ -136,48 +188,41 @@ class RegisterAllocatorTest : public TestWithZone {
     loop_blocks_.pop_back();
   }
 
-  void StartLastBlock() {
-    CHECK(!is_last_block_);
-    is_last_block_ = true;
-    NewBlock();
-  }
-
   void StartBlock() {
-    CHECK(!is_last_block_);
     block_returns_ = false;
     NewBlock();
   }
 
-  void EndBlock(BlockCompletion completion = FallThrough()) {
-    completions_.push_back(completion);
+  int EndBlock(BlockCompletion completion = FallThrough()) {
+    int instruction_index = kMinInt;
+    if (block_returns_) {
+      CHECK(completion.type_ == kBlockEnd || completion.type_ == kFallThrough);
+      completion.type_ = kBlockEnd;
+    }
     switch (completion.type_) {
       case kBlockEnd:
-        CHECK(false);  // unreachable;
         break;
       case kFallThrough:
-        if (is_last_block_ || block_returns_) {
-          completions_.back().type_ = kBlockEnd;
-          break;
-        }
-        EmitFallThrough();
+        instruction_index = EmitFallThrough();
         break;
       case kJump:
         CHECK(!block_returns_);
-        EmitJump();
+        instruction_index = EmitJump();
         break;
       case kBranch:
         CHECK(!block_returns_);
-        EmitBranch(completion.vreg_);
+        instruction_index = EmitBranch(completion.op_);
         break;
     }
+    completions_.push_back(completion);
     CHECK(current_block_ != nullptr);
     sequence()->EndBlock(current_block_->rpo_number());
     current_block_ = nullptr;
+    return instruction_index;
   }
 
   void Allocate() {
     CHECK_EQ(nullptr, current_block_);
-    CHECK(is_last_block_);
     WireBlocks();
     RegisterAllocatorVerifier verifier(zone(), config(), sequence());
     if (FLAG_trace_alloc || FLAG_trace_turbo) {
@@ -195,111 +240,110 @@ class RegisterAllocatorTest : public TestWithZone {
     verifier.VerifyGapMoves();
   }
 
-  int NewReg() { return sequence()->NextVirtualRegister(); }
+  TestOperand Imm(int32_t imm = 0) {
+    int index = sequence()->AddImmediate(Constant(imm));
+    return TestOperand(kImmediate, index);
+  }
 
-  int Parameter() {
-    int vreg = NewReg();
-    InstructionOperand* outputs[1]{UseRegister(vreg)};
-    Emit(kArchNop, 1, outputs);
+  VReg Parameter(TestOperand output_op = Reg()) {
+    VReg vreg = NewReg();
+    InstructionOperand* outputs[1]{ConvertOutputOp(vreg, output_op)};
+    Emit(vreg.value_, kArchNop, 1, outputs);
     return vreg;
   }
 
-  Instruction* Return(int vreg) {
+  int Return(TestOperand input_op_0) {
     block_returns_ = true;
-    InstructionOperand* inputs[1]{UseRegister(vreg)};
-    return Emit(kArchRet, 0, nullptr, 1, inputs);
+    InstructionOperand* inputs[1]{ConvertInputOp(input_op_0)};
+    return Emit(NewIndex(), kArchRet, 0, nullptr, 1, inputs);
   }
 
-  PhiInstruction* Phi(int vreg) {
-    PhiInstruction* phi = new (zone()) PhiInstruction(zone(), NewReg());
-    phi->operands().push_back(vreg);
+  int Return(VReg vreg) { return Return(Reg(vreg, 0)); }
+
+  PhiInstruction* Phi(VReg incoming_vreg) {
+    PhiInstruction* phi = new (zone()) PhiInstruction(zone(), NewReg().value_);
+    phi->operands().push_back(incoming_vreg.value_);
     current_block_->AddPhi(phi);
     return phi;
   }
 
-  int DefineConstant(int32_t imm = 0) {
-    int virtual_register = NewReg();
-    sequence()->AddConstant(virtual_register, Constant(imm));
-    InstructionOperand* outputs[1]{
-        ConstantOperand::Create(virtual_register, zone())};
-    Emit(kArchNop, 1, outputs);
-    return virtual_register;
-  }
-
-  ImmediateOperand* Immediate(int32_t imm = 0) {
-    int index = sequence()->AddImmediate(Constant(imm));
-    return ImmediateOperand::Create(index, zone());
-  }
-
-  Instruction* EmitFRI(int output_vreg, int input_vreg_0) {
-    InstructionOperand* outputs[1]{DefineSameAsFirst(output_vreg)};
-    InstructionOperand* inputs[2]{UseRegister(input_vreg_0), Immediate()};
-    return Emit(kArchNop, 1, outputs, 2, inputs);
+  PhiInstruction* Phi(VReg incoming_vreg_0, VReg incoming_vreg_1) {
+    auto phi = Phi(incoming_vreg_0);
+    Extend(phi, incoming_vreg_1);
+    return phi;
   }
 
-  Instruction* EmitFRU(int output_vreg, int input_vreg_0, int input_vreg_1) {
-    InstructionOperand* outputs[1]{DefineSameAsFirst(output_vreg)};
-    InstructionOperand* inputs[2]{UseRegister(input_vreg_0), Use(input_vreg_1)};
-    return Emit(kArchNop, 1, outputs, 2, inputs);
+  static void Extend(PhiInstruction* phi, VReg vreg) {
+    phi->operands().push_back(vreg.value_);
   }
 
-  Instruction* EmitRRR(int output_vreg, int input_vreg_0, int input_vreg_1) {
-    InstructionOperand* outputs[1]{UseRegister(output_vreg)};
-    InstructionOperand* inputs[2]{UseRegister(input_vreg_0),
-                                  UseRegister(input_vreg_1)};
-    return Emit(kArchNop, 1, outputs, 2, inputs);
+  VReg DefineConstant(int32_t imm = 0) {
+    VReg vreg = NewReg();
+    sequence()->AddConstant(vreg.value_, Constant(imm));
+    InstructionOperand* outputs[1]{
+        ConstantOperand::Create(vreg.value_, zone())};
+    Emit(vreg.value_, kArchNop, 1, outputs);
+    return vreg;
   }
 
- private:
-  InstructionOperand* Unallocated(int vreg,
-                                  UnallocatedOperand::ExtendedPolicy policy) {
-    UnallocatedOperand* op = new (zone()) UnallocatedOperand(policy);
-    op->set_virtual_register(vreg);
-    return op;
+  VReg EmitOII(TestOperand output_op, TestOperand input_op_0,
+               TestOperand input_op_1) {
+    VReg output_vreg = NewReg();
+    InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)};
+    InstructionOperand* inputs[2]{ConvertInputOp(input_op_0),
+                                  ConvertInputOp(input_op_1)};
+    Emit(output_vreg.value_, kArchNop, 1, outputs, 2, inputs);
+    return output_vreg;
   }
 
-  InstructionOperand* Unallocated(int vreg,
-                                  UnallocatedOperand::ExtendedPolicy policy,
-                                  UnallocatedOperand::Lifetime lifetime) {
-    UnallocatedOperand* op = new (zone()) UnallocatedOperand(policy, lifetime);
-    op->set_virtual_register(vreg);
-    return op;
+  VReg EmitCall(TestOperand output_op, size_t input_size, TestOperand* inputs) {
+    VReg output_vreg = NewReg();
+    InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)};
+    InstructionOperand** mapped_inputs =
+        zone()->NewArray<InstructionOperand*>(static_cast<int>(input_size));
+    for (size_t i = 0; i < input_size; ++i) {
+      mapped_inputs[i] = ConvertInputOp(inputs[i]);
+    }
+    Emit(output_vreg.value_, kArchCallCodeObject, 1, outputs, input_size,
+         mapped_inputs);
+    return output_vreg;
   }
 
-  InstructionOperand* UseRegister(int vreg) {
-    return Unallocated(vreg, UnallocatedOperand::MUST_HAVE_REGISTER);
+  // Get defining instruction vreg or value returned at instruction creation
+  // time when there is no return value.
+  const Instruction* GetInstruction(int instruction_index) {
+    auto it = instructions_.find(instruction_index);
+    CHECK(it != instructions_.end());
+    return it->second;
   }
 
-  InstructionOperand* DefineSameAsFirst(int vreg) {
-    return Unallocated(vreg, UnallocatedOperand::SAME_AS_FIRST_INPUT);
-  }
+ private:
+  VReg NewReg() { return VReg(sequence()->NextVirtualRegister()); }
+  int NewIndex() { return current_instruction_index_--; }
 
-  InstructionOperand* Use(int vreg) {
-    return Unallocated(vreg, UnallocatedOperand::NONE,
-                       UnallocatedOperand::USED_AT_START);
-  }
+  static TestOperand Invalid() { return TestOperand(kInvalid, VReg()); }
 
-  void EmitBranch(int vreg) {
-    InstructionOperand* inputs[4]{UseRegister(vreg), Immediate(), Immediate(),
-                                  Immediate()};
+  int EmitBranch(TestOperand input_op) {
+    InstructionOperand* inputs[4]{ConvertInputOp(input_op),
+                                  ConvertInputOp(Imm()), ConvertInputOp(Imm()),
+                                  ConvertInputOp(Imm())};
     InstructionCode opcode = kArchJmp | FlagsModeField::encode(kFlags_branch) |
                              FlagsConditionField::encode(kEqual);
-    Instruction* instruction =
+    auto* instruction =
         NewInstruction(opcode, 0, nullptr, 4, inputs)->MarkAsControl();
-    sequence()->AddInstruction(instruction);
+    return AddInstruction(NewIndex(), instruction);
   }
 
-  void EmitFallThrough() {
-    Instruction* instruction =
-        NewInstruction(kArchNop, 0, nullptr)->MarkAsControl();
-    sequence()->AddInstruction(instruction);
+  int EmitFallThrough() {
+    auto* instruction = NewInstruction(kArchNop, 0, nullptr)->MarkAsControl();
+    return AddInstruction(NewIndex(), instruction);
   }
 
-  void EmitJump() {
-    InstructionOperand* inputs[1]{Immediate()};
-    Instruction* instruction =
+  int EmitJump() {
+    InstructionOperand* inputs[1]{ConvertInputOp(Imm())};
+    auto* instruction =
         NewInstruction(kArchJmp, 0, nullptr, 1, inputs)->MarkAsControl();
-    sequence()->AddInstruction(instruction);
+    return AddInstruction(NewIndex(), instruction);
   }
 
   Instruction* NewInstruction(InstructionCode code, size_t outputs_size,
@@ -313,21 +357,83 @@ class RegisterAllocatorTest : public TestWithZone {
                             inputs, temps_size, temps);
   }
 
-  Instruction* Emit(InstructionCode code, size_t outputs_size,
-                    InstructionOperand** outputs, size_t inputs_size = 0,
-                    InstructionOperand* *inputs = nullptr,
-                    size_t temps_size = 0,
-                    InstructionOperand* *temps = nullptr) {
-    Instruction* instruction = NewInstruction(
-        code, outputs_size, outputs, inputs_size, inputs, temps_size, temps);
-    sequence()->AddInstruction(instruction);
-    return instruction;
+  InstructionOperand* Unallocated(TestOperand op,
+                                  UnallocatedOperand::ExtendedPolicy policy) {
+    auto* unallocated = new (zone()) UnallocatedOperand(policy);

[Benedikt Meurer, 2014/11/13 09:22:04]

auto* looks weird, how about auto instead? :-)

+    unallocated->set_virtual_register(op.vreg_.value_);
+    return unallocated;
+  }
+
+  InstructionOperand* Unallocated(TestOperand op,
+                                  UnallocatedOperand::ExtendedPolicy policy,
+                                  UnallocatedOperand::Lifetime lifetime) {
+    auto* unallocated = new (zone()) UnallocatedOperand(policy, lifetime);
+    unallocated->set_virtual_register(op.vreg_.value_);
+    return unallocated;
+  }
+
+  InstructionOperand* Unallocated(TestOperand op,
+                                  UnallocatedOperand::ExtendedPolicy policy,
+                                  int index) {
+    auto* unallocated = new (zone()) UnallocatedOperand(policy, index);
+    unallocated->set_virtual_register(op.vreg_.value_);
+    return unallocated;
+  }
+
+  InstructionOperand* Unallocated(TestOperand op,
+                                  UnallocatedOperand::BasicPolicy policy,
+                                  int index) {
+    auto* unallocated = new (zone()) UnallocatedOperand(policy, index);
+    unallocated->set_virtual_register(op.vreg_.value_);
+    return unallocated;
+  }
+
+  InstructionOperand* ConvertInputOp(TestOperand op) {
+    if (op.type_ == kImmediate) {
+      CHECK_EQ(op.vreg_.value_, kNoValue);
+      return ImmediateOperand::Create(op.value_, zone());
+    }
+    CHECK_NE(op.vreg_.value_, kNoValue);
+    switch (op.type_) {
+      case kNone:
+        return Unallocated(op, UnallocatedOperand::NONE,
+                           UnallocatedOperand::USED_AT_START);
+      case kRegister:
+        return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER,
+                           UnallocatedOperand::USED_AT_START);
+      case kFixedRegister:
+        CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
+        return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
+      default:
+        break;
+    }
+    CHECK(false);
+    return NULL;
+  }
+
+  InstructionOperand* ConvertOutputOp(VReg vreg, TestOperand op) {
+    CHECK_EQ(op.vreg_.value_, kNoValue);
+    op.vreg_ = vreg;
+    switch (op.type_) {
+      case kSameAsFirst:
+        return Unallocated(op, UnallocatedOperand::SAME_AS_FIRST_INPUT);
+      case kRegister:
+        return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER);
+      case kFixedSlot:
+        return Unallocated(op, UnallocatedOperand::FIXED_SLOT, op.value_);
+      case kFixedRegister:
+        CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
+        return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
+      default:
+        break;
+    }
+    CHECK(false);
+    return NULL;
   }
 
   InstructionBlock* NewBlock() {
     CHECK(current_block_ == nullptr);
-    BasicBlock::Id block_id =
-        BasicBlock::Id::FromSize(instruction_blocks_.size());
+    auto block_id = BasicBlock::Id::FromSize(instruction_blocks_.size());
     Rpo rpo = Rpo::FromInt(block_id.ToInt());
     Rpo loop_header = Rpo::Invalid();
     Rpo loop_end = Rpo::Invalid();
@@ -347,7 +453,7 @@ class RegisterAllocatorTest : public TestWithZone {
       }
     }
     // Construct instruction block.
-    InstructionBlock* instruction_block = new (zone()) InstructionBlock(
+    auto* instruction_block = new (zone()) InstructionBlock(
         zone(), block_id, rpo, rpo, loop_header, loop_end, false);
     instruction_blocks_.push_back(instruction_block);
     current_block_ = instruction_block;
@@ -380,17 +486,33 @@ class RegisterAllocatorTest : public TestWithZone {
         block_offset + static_cast<size_t>(jump_offset);
     CHECK(block_offset < instruction_blocks_.size());
     CHECK(target_block_offset < instruction_blocks_.size());
-    InstructionBlock* block = instruction_blocks_[block_offset];
-    InstructionBlock* target = instruction_blocks_[target_block_offset];
+    auto* block = instruction_blocks_[block_offset];
+    auto* target = instruction_blocks_[target_block_offset];
     block->successors().push_back(target->rpo_number());
     target->predecessors().push_back(block->rpo_number());
   }
 
+  int Emit(int instruction_index, InstructionCode code, size_t outputs_size,
+           InstructionOperand** outputs, size_t inputs_size = 0,
+           InstructionOperand* *inputs = nullptr, size_t temps_size = 0,
+           InstructionOperand* *temps = nullptr) {
+    auto* instruction = NewInstruction(code, outputs_size, outputs, inputs_size,
+                                       inputs, temps_size, temps);
+    return AddInstruction(instruction_index, instruction);
+  }
+
+  int AddInstruction(int instruction_index, Instruction* instruction) {
+    sequence()->AddInstruction(instruction);
+    return instruction_index;
+  }
+
   struct LoopData {
     Rpo loop_header_;
     int expected_blocks_;
   };
+
   typedef std::vector<LoopData> LoopBlocks;
+  typedef std::map<int, const Instruction*> Instructions;
   typedef std::vector<BlockCompletion> Completions;
 
   SmartPointer<RegisterConfiguration> config_;
@@ -402,45 +524,42 @@ class RegisterAllocatorTest : public TestWithZone {
 
   // Block building state.
   InstructionBlocks instruction_blocks_;
+  Instructions instructions_;
+  int current_instruction_index_;
   Completions completions_;
   LoopBlocks loop_blocks_;
   InstructionBlock* current_block_;
-  bool is_last_block_;
   bool block_returns_;
 };
 
 
 TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) {
-  StartLastBlock();
-  int a_reg = Parameter();
-  int b_reg = Parameter();
-  int c_reg = NewReg();
-  Instruction* res = EmitRRR(c_reg, a_reg, b_reg);
+  // return p0 + p1;
+  StartBlock();
+  auto a_reg = Parameter();
+  auto b_reg = Parameter();
+  auto c_reg = EmitOII(Reg(1), Reg(a_reg, 1), Reg(b_reg, 0));
   Return(c_reg);
-  EndBlock();
+  EndBlock(Last());
 
   Allocate();
-
-  ASSERT_TRUE(res->OutputAt(0)->IsRegister());
 }
 
 
 TEST_F(RegisterAllocatorTest, SimpleLoop) {
   // i = K;
   // while(true) { i++ }
-
   StartBlock();
-  int i_reg = DefineConstant();
+  auto i_reg = DefineConstant();
   EndBlock();
 
   {
     StartLoop(1);
 
-    StartLastBlock();
-    PhiInstruction* phi = Phi(i_reg);
-    int ipp = NewReg();
-    EmitFRU(ipp, phi->virtual_register(), DefineConstant());
-    phi->operands().push_back(ipp);
+    StartBlock();
+    auto* phi = Phi(i_reg);
+    auto ipp = EmitOII(Same(), Reg(phi), Use(DefineConstant()));
+    Extend(phi, ipp);
     EndBlock(Jump(0));
 
     EndLoop();
@@ -453,15 +572,127 @@ TEST_F(RegisterAllocatorTest, SimpleLoop) {
 TEST_F(RegisterAllocatorTest, SimpleBranch) {
   // return i ? K1 : K2
   StartBlock();
-  int i_reg = DefineConstant();
-  EndBlock(Branch(i_reg, 1, 2));
+  auto i = DefineConstant();
+  EndBlock(Branch(Reg(i), 1, 2));
 
   StartBlock();
   Return(DefineConstant());
-  EndBlock();
+  EndBlock(Last());
 
-  StartLastBlock();
+  StartBlock();
   Return(DefineConstant());
+  EndBlock(Last());
+
+  Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, SimpleDiamond) {
+  // return p0 ? p0 : p0
+  StartBlock();
+  auto param = Parameter();
+  EndBlock(Branch(Reg(param), 1, 2));
+
+  StartBlock();
+  EndBlock(Jump(2));
+
+  StartBlock();
+  EndBlock(Jump(1));
+
+  StartBlock();
+  Return(param);
+  EndBlock();
+
+  Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, SimpleDiamondPhi) {
+  // return i ? K1 : K2
+  StartBlock();
+  EndBlock(Branch(Reg(DefineConstant()), 1, 2));
+
+  StartBlock();
+  auto t_val = DefineConstant();
+  EndBlock(Jump(2));
+
+  StartBlock();
+  auto f_val = DefineConstant();
+  EndBlock(Jump(1));
+
+  StartBlock();
+  Return(Reg(Phi(t_val, f_val)));
+  EndBlock();
+
+  Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, DiamondManyPhis) {
+  const int kPhis = kDefaultNRegs * 2;
+
+  StartBlock();
+  EndBlock(Branch(Reg(DefineConstant()), 1, 2));
+
+  StartBlock();
+  VReg t_vals[kPhis];
+  for (int i = 0; i < kPhis; ++i) {
+    t_vals[i] = DefineConstant();
+  }
+  EndBlock(Jump(2));
+
+  StartBlock();
+  VReg f_vals[kPhis];
+  for (int i = 0; i < kPhis; ++i) {
+    f_vals[i] = DefineConstant();
+  }
+  EndBlock(Jump(1));
+
+  StartBlock();
+  TestOperand merged[kPhis];
+  for (int i = 0; i < kPhis; ++i) {
+    merged[i] = Use(Phi(t_vals[i], f_vals[i]));
+  }
+  Return(EmitCall(Reg(), kPhis, merged));
+  EndBlock();
+
+  Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, DoubleDiamondManyRedundantPhis) {
+  const int kPhis = kDefaultNRegs * 2;
+
+  // First diamond.
+  StartBlock();
+  VReg vals[kPhis];
+  for (int i = 0; i < kPhis; ++i) {
+    vals[i] = Parameter(Slot(i));
+  }
+  EndBlock(Branch(Reg(DefineConstant()), 1, 2));
+
+  StartBlock();
+  EndBlock(Jump(2));
+
+  StartBlock();
+  EndBlock(Jump(1));
+
+  // Second diamond.
+  StartBlock();
+  EndBlock(Branch(Reg(DefineConstant()), 1, 2));
+
+  StartBlock();
+  EndBlock(Jump(2));
+
+  StartBlock();
+  EndBlock(Jump(1));
+
+  StartBlock();
+  TestOperand merged[kPhis];
+  for (int i = 0; i < kPhis; ++i) {
+    merged[i] = Use(Phi(vals[i], vals[i]));
+  }
+  Return(EmitCall(Reg(), kPhis, merged));
   EndBlock();
 
   Allocate();
@@ -471,14 +702,12 @@ TEST_F(RegisterAllocatorTest, SimpleBranch) {
 TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
   const size_t kNumRegs = 3;
   const size_t kParams = kNumRegs + 1;
-  int parameters[kParams];
-
   // Override number of registers.
   SetNumRegs(kNumRegs, kNumRegs);
 
-  // Initial block.
   StartBlock();
-  int constant = DefineConstant();
+  auto constant = DefineConstant();
+  VReg parameters[kParams];
   for (size_t i = 0; i < arraysize(parameters); ++i) {
     parameters[i] = DefineConstant();
   }
@@ -498,12 +727,11 @@ TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
     // Perform some computations.
     // something like phi[i] += const
     for (size_t i = 0; i < arraysize(parameters); ++i) {
-      int result = NewReg();
-      EmitFRU(result, phis[i]->virtual_register(), constant);
-      phis[i]->operands().push_back(result);
+      auto result = EmitOII(Same(), Reg(phis[i]), Use(constant));
+      Extend(phis[i], result);
     }
 
-    EndBlock(Branch(DefineConstant(), 1, 2));
+    EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 
     // Jump back to loop header.
     StartBlock();
@@ -512,10 +740,7 @@ TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
     EndLoop();
   }
 
-  // End block.
-  StartLastBlock();
-
-  // Return sum.
+  StartBlock();
   Return(DefineConstant());
   EndBlock();