Convert diamond shaped control flow into a single conditional instruction.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 3912 matching lines @@
   UNREACHABLE();
 }
 
 
 void ConstantPropagator::VisitStoreLocal(StoreLocalInstr* instr) {
   // Instruction is eliminated when translating to SSA.
   UNREACHABLE();
 }
 
 
+void ConstantPropagator::VisitIfThenElse(IfThenElseInstr* instr) {
+  const Object& left = instr->left()->definition()->constant_value();
+  const Object& right = instr->right()->definition()->constant_value();
+
+  if (IsNonConstant(left) || IsNonConstant(right)) {
+    // TODO(vegorov): incorporate nullability information into the lattice.

[Florian Schneider, 2013/04/10 13:59:50]

Maybe check Token::IsEqualityOperator(kind()) even if it only supports equality
right now.

[Vyacheslav Egorov (Google), 2013/04/10 14:51:32]

Done.

+    if ((left.IsNull() && instr->right()->Type()->HasDecidableNullability()) ||
+        (right.IsNull() && instr->left()->Type()->HasDecidableNullability())) {
+      bool result = left.IsNull() ? instr->right()->Type()->IsNull()
+                                  : instr->left()->Type()->IsNull();
+      if (instr->kind() == Token::kNE_STRICT ||
+          instr->kind() == Token::kNE) {
+        result = !result;
+      }
+      SetValue(instr, Smi::Handle(
+          Smi::New(result ? instr->if_true() : instr->if_false())));
+    } else {
+      SetValue(instr, non_constant_);
+    }
+  } else if (IsConstant(left) && IsConstant(right)) {
+    bool result = (left.raw() == right.raw());
+    if (instr->kind() == Token::kNE_STRICT ||
+        instr->kind() == Token::kNE) {
+      result = !result;
+    }
+    SetValue(instr, Smi::Handle(
+        Smi::New(result ? instr->if_true() : instr->if_false())));
+  }
+}
+
+
 void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
 
   if (IsNonConstant(left) || IsNonConstant(right)) {
     // TODO(vegorov): incorporate nullability information into the lattice.
     if ((left.IsNull() && instr->right()->Type()->HasDecidableNullability()) ||
         (right.IsNull() && instr->left()->Type()->HasDecidableNullability())) {
       bool result = left.IsNull() ? instr->right()->Type()->IsNull()
                                   : instr->left()->Type()->IsNull();
@@ skipping 799 matching lines @@
 
   if (changed) {
     // We may have changed the block order and the dominator tree.
     flow_graph->DiscoverBlocks();
     GrowableArray<BitVector*> dominance_frontier;
     flow_graph->ComputeDominators(&dominance_frontier);
   }
 }
 
 
+static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) {
+  return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) &&
+    ((block->next() == block->last_instruction()) ||
+     ((block->next() == defn) && (defn->next() == block->last_instruction())));
+}
+
+
+static void EliminateTrivialBlock(BlockEntryInstr* block,
+                                  Definition* instr,
+                                  IfThenElseInstr* before) {
+  block->UnuseAllInputs();
+  block->last_instruction()->UnuseAllInputs();
+
+  if ((block->next() == instr) &&
+      (instr->next() == block->last_instruction())) {
+    before->previous()->LinkTo(instr);
+    instr->LinkTo(before);
+  }
+}
+
+
+void IfConverter::Simplify(FlowGraph* flow_graph) {
+  if (!IfThenElseInstr::IsSupported()) {
+    return;
+  }
+
+  bool changed = false;
+
+  const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder();
+  for (BlockIterator it(postorder); !it.Done(); it.Advance()) {
+    BlockEntryInstr* block = it.Current();
+    JoinEntryInstr* join = block->AsJoinEntry();
+
+    // Detect diamond control flow pattern which materializes a value depending
+    // on the result of the comparison:
+    //
+    // Ba:
+    //   ...
+    //   Branch if COMP goto (Bb, Bc)
+    // Bb: -- trivial block that contains at most one definition
+    //   c1 = Constant(...)
+    //   goto Bd
+    // Bc: -- trivial block that contains at most one definition
+    //   c2 = Constant(...)
+    //   goto Bd
+    // Bd:
+    //   v = phi(c1, c2) -- single phi
+    //
+    // and replace it with
+    //
+    // Ba:
+    //   v = IfThenElse(COMP ? c1 : c2)
+    //
+    if ((join != NULL) &&
+        (join->phis() != NULL) &&
+        (join->phis()->length() == 1) &&
+        (block->PredecessorCount() == 2)) {
+      BlockEntryInstr* pred1 = block->PredecessorAt(0);

[Florian Schneider, 2013/04/10 13:59:50]

Why not use the same names as in the comments for all the blocks (ba, bb, bc and
bd)?

[Vyacheslav Egorov (Google), 2013/04/10 14:51:32]

Changed names in the comment to reflect naming in the code.

+      BlockEntryInstr* pred2 = block->PredecessorAt(1);
+
+      PhiInstr* phi = (*join->phis())[0];
+      Value* v1 = phi->InputAt(0);
+      Value* v2 = phi->InputAt(1);
+
+      if (IsTrivialBlock(pred1, v1->definition()) &&
+          IsTrivialBlock(pred2, v2->definition()) &&
+          (pred1->PredecessorAt(0) == pred2->PredecessorAt(0))) {
+        BlockEntryInstr* pred = pred1->PredecessorAt(0);
+        BranchInstr* branch = pred->last_instruction()->AsBranch();
+        ComparisonInstr* comparison = branch->comparison();
+
+        // Check if the platform supports efficient branchless IfThenElseInstr
+        // for the given combination of comparison and values flowing from
+        // false and true paths.
+        if (IfThenElseInstr::Supports(comparison, v1, v2)) {

[Florian Schneider, 2013/04/10 13:59:50]

I think the code becomes simpler with an early return here:

if (!IfThenElseInstr::Supports(comparison, v1, v2)) return;

Then you can get rid of the changed flag, too.

[Vyacheslav Egorov (Google), 2013/04/10 14:51:32]

Can't use early return (there is a loop around this code).

Could have used continue but I find inverted conditions hard to read. 

It'll be cool if we were writing compiler in a language with pattern matching,
but alas...

+          Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2;
+          Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2;
+
+          IfThenElseInstr* if_then_else = new IfThenElseInstr(
+              comparison->kind(),
+              comparison->InputAt(0)->Copy(),
+              comparison->InputAt(1)->Copy(),
+              if_true->Copy(),
+              if_false->Copy());
+          flow_graph->InsertBefore(branch,
+                                   if_then_else,
+                                   NULL,
+                                   Definition::kValue);
+
+          phi->ReplaceUsesWith(if_then_else);
+
+          // Connect IfThenElseInstr to the first instruction in the merge block
+          // effectively eliminating diamond control flow.
+          // Current block as well as pred1 and pred2 blocks are no longer in
+          // the graph at this point.
+          if_then_else->LinkTo(join->next());
+          pred->set_last_instruction(join->last_instruction());
+
+          // Resulting block must inherit block id from the eliminated current
+          // block to guarantee that ordering of phi operands in its successor
+          // stays consistent.
+          pred->set_block_id(block->block_id());
+
+          // If v1 and v2 were defined inside eliminated blocks pred1/pred2
+          // move them out to the place before inserted IfThenElse instruction.
+          EliminateTrivialBlock(pred1, v1->definition(), if_then_else);
+          EliminateTrivialBlock(pred2, v2->definition(), if_then_else);
+
+          // Update use lists to reflect changes in the graph.
+          phi->UnuseAllInputs();
+          branch->UnuseAllInputs();
+
+          // The graph has changed. Recompute dominators and block orders after
+          // this pass is finished.
+          changed = true;
+        }
+      }
+    }
+  }
+
+  if (changed) {
+    // We may have changed the block order and the dominator tree.
+    flow_graph->DiscoverBlocks();
+    GrowableArray<BitVector*> dominance_frontier;
+    flow_graph->ComputeDominators(&dominance_frontier);
+  }
+}
+
+
 }  // namespace dart