Fuse compare with branch at graph building time.

runtime/vm/flow_graph_builder.cc

Index: runtime/vm/flow_graph_builder.cc
===================================================================
--- runtime/vm/flow_graph_builder.cc	(revision 9728)
+++ runtime/vm/flow_graph_builder.cc	(working copy)
@@ -243,18 +243,67 @@
 }
 
 
+// TODO(srdjan): This code is clumsy. Try to skip allocation of ComparisonComp

[Kevin Millikin (Google), 2012/07/19 12:28:05]

A way to do this is to implement TestGraphVisitor::ReturnComputation to inspect
the computation and if it matches the pattern add the branch instead (when
!FLAG_enable_type_checks, I suppose).

We would lose our handling of negation, but that can work too: negation in a
test context is just flipping the labels.

+// and generate the right BranchInstr directly.
+// Replaces instruction patterns:
+//   t0 <- Comparison(kind, t0, t1)
+//   t1 <- #true
+//   Branch if t0 === t1 goto (true, false)
+// With:
+//   Branch if t0 kind t1 goto (true, false)
+// Returns false if fusing is not possible, e.g:
+//   t0 <- LoadLocal
+//   t1 <- #true
+//   Branch if t0 === t1 goto (true, false)
+static bool TryFuseBranchInstr(BranchInstr* branch) {
+  UseVal* use = branch->left()->AsUse();
+  if (use == NULL) return false;
+  BindInstr* compare_instr = use->definition()->AsBind();
+  if (compare_instr == NULL) return false;
+  ComparisonComp* compare = compare_instr->computation()->AsComparison();
+  Token::Kind kind;
+  if (compare == NULL) {
+    // Check if there is a BooleanNegate in between Comparison and Branch.
+    BooleanNegateComp* neg = compare_instr->computation()->AsBooleanNegate();
+    if (neg == NULL) return false;
+    compare_instr = compare_instr->previous()->AsBind();

[Kevin Millikin (Google), 2012/07/19 12:28:05]

I guess previous() is non-NULL because boolean negate has an input operand and
we always materialize constants so the operand is always in the instruction
stream before the negate.

I'm a bit uncomfortable relying on that --- the graph is only partly constructed
so assuming too much about it constrains us.  (I'm actually uncomfortable
rewriting the graph this way during construction in general.  My experience is
that it leads to a lot of headaches.)

[srdjan, 2012/07/19 15:33:58]

Agree.

Added another test:
if (compare_instr->previous() == NULL) return false;

Yes, the AST variations are pretty limited and known. I am also uncomfortable
doing it that way and will fix it. This way is too fragile as it depends too
much on how we exactly generate AST. 

+    ASSERT(compare_instr != NULL);
+    compare = compare_instr->computation()->AsComparison();
+    if (compare == NULL) return false;
+    // Negation can be handled only in connection with EqualityCompare.
+    if (!compare->IsEqualityCompare()) return false;
+    kind = Token::kNE;
+  } else {
+    kind = compare->kind();
+  }
+  branch->set_kind(kind);
+  branch->SetInputAt(0, compare->InputAt(0));
+  branch->SetInputAt(1, compare->InputAt(1));
+  // Remove elminated nodes.
+  branch->set_previous(compare_instr->previous());
+  compare_instr->previous()->set_next(branch);
+  return true;
+}
 
+
 void TestGraphVisitor::ReturnValue(Value* value) {
   if (FLAG_enable_type_checks) {
     value = Bind(new AssertBooleanComp(condition_token_pos(),
                                        owner()->try_index(),
                                        value));
   }
-  BranchInstr* branch = new BranchInstr(value);
+  const Bool& bool_true = Bool::ZoneHandle(Bool::True());
+  Value* constant_true = Bind(new ConstantVal(bool_true));
+  BranchInstr* branch = new BranchInstr(condition_token_pos(),
+                                        owner()->try_index(),
+                                        value,
+                                        constant_true,
+                                        Token::kEQ_STRICT);
   AddInstruction(branch);
   CloseFragment();
   true_successor_address_ = branch->true_successor_address();
   false_successor_address_ = branch->false_successor_address();
+  TryFuseBranchInstr(branch);
 }