Introduce Goto instructions to the flow graph.

runtime/vm/intermediate_language.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 240 matching lines @@
 
 void ThrowInstr::SetInputAt(intptr_t i, Value* value) {
   if (i == 0) {
     exception_ = value;
     return;
   }
   UNREACHABLE();
 }
 
 
+intptr_t GotoInstr::InputCount() const {
+  return 0;
+}
+
+
+Value* GotoInstr::InputAt(intptr_t i) const {
+  UNREACHABLE();
+  return NULL;
+}
+
+
+void GotoInstr::SetInputAt(intptr_t i, Value* value) {
+  UNREACHABLE();
+}
+
+
 intptr_t ReturnInstr::InputCount() const {
   return 1;
 }
 
 
 Value* ReturnInstr::InputAt(intptr_t i) const {
   if (i == 0) return value();
   UNREACHABLE();
   return NULL;
 }
@@ skipping 209 matching lines @@
   ASSERT(next() != NULL);
   Instruction* next_instr = next();
   if (next_instr->IsBlockEntry()) {
     set_last_instruction(this);
   } else {
     while ((next_instr != NULL) &&
            !next_instr->IsBlockEntry() &&
            !next_instr->IsBranch()) {
       if (vars != NULL) next_instr->RecordAssignedVars(vars);
       set_last_instruction(next_instr);
-      next_instr = next_instr->next();
+      GotoInstr* goto_instr = next_instr->AsGoto();
+      next_instr =
+          (goto_instr != NULL) ? goto_instr->successor() : next_instr->next();
     }
   }
   if (next_instr != NULL) {
     next_instr->DiscoverBlocks(this, preorder, postorder,
                                parent, assigned_vars, variable_count);
   }
 
   // 6. Assign postorder number and add the block entry to the list.
   set_postorder_number(postorder->length());
   postorder->Add(this);
@@ skipping 31 matching lines @@
       phis_->Add(NULL);
     }
   }
   ASSERT((*phis_)[var_index] == NULL);
   (*phis_)[var_index] = new PhiInstr(PredecessorCount());
   phi_count_++;
 }
 
 
 intptr_t Instruction::SuccessorCount() const {
-  ASSERT(next() == NULL || next()->IsBlockEntry());
-  return (next() != NULL) ? 1 : 0;
+  return 0;
 }
 
 
 BlockEntryInstr* Instruction::SuccessorAt(intptr_t index) const {
-  return next()->AsBlockEntry();
+  // Called only if index is in range.  Only control-transfer instructions
+  // can have non-zero successor counts and they override this function.
+  UNREACHABLE();
+  return NULL;
 }
 
 
 intptr_t GraphEntryInstr::SuccessorCount() const {
   return 1 + catch_entries_.length();
 }
 
 
 BlockEntryInstr* GraphEntryInstr::SuccessorAt(intptr_t index) const {
   if (index == 0) return normal_entry_;
   return catch_entries_[index - 1];
 }
 
 
 intptr_t BranchInstr::SuccessorCount() const {
   return 2;
 }
 
 
 BlockEntryInstr* BranchInstr::SuccessorAt(intptr_t index) const {
   if (index == 0) return true_successor_;
   if (index == 1) return false_successor_;
   UNREACHABLE();
   return NULL;
 }
 
 
+intptr_t GotoInstr::SuccessorCount() const {
+  return 1;
+}
+
+
+BlockEntryInstr* GotoInstr::SuccessorAt(intptr_t index) const {
+  ASSERT(index == 0);
+  return successor();
+}
+
+
+void Instruction::Goto(JoinEntryInstr* entry) {

[srdjan, 2012/07/12 16:42:26]

IMO, renaming it to AppendGoto will make the call sites more readable.
Can a Goto be appended to any instruction, i..e, do you need asserts to restrict
appending?

[Kevin Millikin (Google), 2012/07/13 15:34:59]

It's kind of messy right now.  There are asserts in set_next that cover the
disallowed cases.

+  set_next(new GotoInstr(entry));
+}
+
+
 // ==== Support for propagating static type.
 RawAbstractType* ConstantVal::StaticType() const {
   if (value().IsInstance()) {
     return Instance::Cast(value()).GetType();
   } else {
     UNREACHABLE();
     return AbstractType::null();
   }
 }
 
@@ skipping 394 matching lines @@
   ASSERT(exception()->IsUse());
   ASSERT(stack_trace()->IsUse());
   compiler->GenerateCallRuntime(cid(),
                                 token_pos(),
                                 try_index(),
                                 kReThrowRuntimeEntry);
   __ int3();
 }
 
 
+LocationSummary* GotoInstr::MakeLocationSummary() const {
+  return new LocationSummary(0, 0);
+}
+
+
+void GotoInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  compiler->frame_register_allocator()->Spill();

[srdjan, 2012/07/12 16:42:26]

It looks strange to do spilling inside EmitNativeCode. Shouldn't this be handled
by register allocator?

[Vyacheslav Egorov (Google), 2012/07/13 14:41:42]

I agree with Srdjan. This way we have discrepancy between the way we handle
Branch (in the register allocator) and Goto (here).

[Kevin Millikin (Google), 2012/07/13 15:34:59]

I think so.  Right now, it's hardcoded into the compiler.  I just moved this
from the driver loop to the native code for Goto (since we didn't have goto
before).

Leaving it in the driver loop requires an explicit check for IsGoto(), which
seems like it should get rolled into one of the virtual functions on the
instruction.

It seems redundant to me anyway, since we also spill at basic block entries. 
I'll sort that out in another change.

[Kevin Millikin (Google), 2012/07/13 15:41:32]

I agree with you both that this is fishy.  It was already that way and I just
moved it around.

It was previously hardcoded in the compiler's VisitBlocks loop, at the end of
every basic block that ended with Goto just before the (hardcoded) jmp.

I can move it back there, or leave it here.

[srdjan, 2012/07/13 23:18:33]

I am fine with a solution that you and Slava agree with.

+  // We can fall through if the successor is the next block in the list.
+  // Otherwise, we need a jump.
+  if (!compiler->IsNextBlock(successor())) {
+    __ jmp(compiler->GetBlockLabel(successor()));
+  }
+}
+
+
 LocationSummary* BranchInstr::MakeLocationSummary() const {
   if (is_fused_with_comparison()) {
     return fused_with_comparison_->locs();
   } else {
     const int kNumInputs = 1;
     const int kNumTemps = 0;
     LocationSummary* locs = new LocationSummary(kNumInputs,
                                                 kNumTemps,
                                                 LocationSummary::kNoCall);
     locs->set_in(0, Location::RequiresRegister());
@@ skipping 308 matching lines @@
   const ExternalLabel label(closure_function.ToCString(), stub.EntryPoint());
   compiler->GenerateCall(token_pos(), try_index(), &label,
                          PcDescriptors::kOther);
   __ Drop(2);  // Discard type arguments and receiver.
 }
 
 
 #undef __
 
 }  // namespace dart