Convert diamond shaped control flow into a single conditional instruction.

runtime/vm/intermediate_language_x64.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/globals.h"  // Needed here to get TARGET_ARCH_X64.
 #if defined(TARGET_ARCH_X64)
 
 #include "vm/intermediate_language.h"
 
 #include "lib/error.h"
@@ skipping 95 matching lines @@
   __ nop(1);
   __ nop(1);
   __ nop(1);
   __ nop(1);
   compiler->AddCurrentDescriptor(PcDescriptors::kReturn,
                                  Isolate::kNoDeoptId,
                                  token_pos());
 }
 
 
+static Condition NegateCondition(Condition condition) {
+  switch (condition) {
+    case EQUAL:         return NOT_EQUAL;
+    case NOT_EQUAL:     return EQUAL;
+    case LESS:          return GREATER_EQUAL;
+    case LESS_EQUAL:    return GREATER;
+    case GREATER:       return LESS_EQUAL;
+    case GREATER_EQUAL: return LESS;
+    case BELOW:         return ABOVE_EQUAL;
+    case BELOW_EQUAL:   return ABOVE;
+    case ABOVE:         return BELOW_EQUAL;
+    case ABOVE_EQUAL:   return BELOW;
+    default:
+      OS::Print("Error %d\n", condition);
+      UNIMPLEMENTED();
+      return EQUAL;
+  }
+}
+
+
+static bool BindsToSmiConstant(Value* val, intptr_t* smi_value) {
+  if (!val->BindsToConstant()) {
+    return false;
+  }
+
+  const Object& bound_constant = val->BoundConstant();
+  if (!bound_constant.IsSmi()) {
+    return false;
+  }
+
+  *smi_value = Smi::Cast(bound_constant).Value();
+  return true;
+}
+
+
+// Detect pattern when one value is zero and another is a power of 2.
+static bool IsPowerOfTwoKind(intptr_t v1, intptr_t v2) {
+  return (Utils::IsPowerOfTwo(v1) && (v2 == 0)) ||
+         (Utils::IsPowerOfTwo(v2) && (v1 == 0));
+}
+
+
+// Detect pattern when one value is increment of another.
+static bool IsIncrementKind(intptr_t v1, intptr_t v2) {
+  return ((v1 == v2 + 1) || (v1 + 1 == v2));
+}
+
+
+bool IfThenElseInstr::IsSupported() {
+  return true;
+}
+
+
+bool IfThenElseInstr::Supports(ComparisonInstr* comparison,
+                               Value* v1,
+                               Value* v2) {
+  if (!(comparison->IsStrictCompare() &&
+        !comparison->AsStrictCompare()->needs_number_check()) &&
+      !(comparison->IsEqualityCompare() &&
+        (comparison->AsEqualityCompare()->receiver_class_id() == kSmiCid))) {
+    return false;
+  }
+
+  intptr_t v1_value, v2_value;
+
+  if (!BindsToSmiConstant(v1, &v1_value) ||
+      !BindsToSmiConstant(v2, &v2_value)) {
+    return false;
+  }
+
+  if (IsPowerOfTwoKind(v1_value, v2_value) ||
+      IsIncrementKind(v1_value, v2_value)) {
+    return true;
+  }
+
+  return false;
+}
+
+
+LocationSummary* IfThenElseInstr::MakeLocationSummary() const {
+  const intptr_t kNumInputs = 2;
+  const intptr_t kNumTemps = 0;
+  LocationSummary* locs =
+      new LocationSummary(kNumInputs, kNumTemps, LocationSummary::kNoCall);
+  locs->set_in(0, Location::RegisterOrConstant(left()));
+  locs->set_in(1, Location::RegisterOrConstant(right()));
+  // TODO(vegorov): support byte register constraints in the register allocator.
+  locs->set_out(Location::RegisterLocation(RDX));
+  return locs;
+}
+
+
+void IfThenElseInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  ASSERT(locs()->out().reg() == RDX);
+  ASSERT((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kEQ) ||
+         (kind_ == Token::kNE_STRICT) || (kind_ == Token::kNE));
+
+  Location left = locs()->in(0);
+  Location right = locs()->in(1);
+  ASSERT(!left.IsConstant() || !right.IsConstant());
+
+  // Clear upper part of the out register. We are going to use setcc on it
+  // which is a byte move.
+  __ xorq(RDX, RDX);
+
+  // Compare left and right. For now only equality comparison is supported.
+  // TODO(vegorov): reuse code from the other comparison instructions instead of
+  // generating it inline here.
+  if (left.IsConstant()) {
+    __ CompareObject(right.reg(), left.constant());
+  } else if (right.IsConstant()) {
+    __ CompareObject(left.reg(), right.constant());
+  } else {
+    __ cmpq(left.reg(), right.reg());
+  }
+
+  Condition true_condition =
+      ((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kEQ)) ? EQUAL
+                                                              : NOT_EQUAL;
+
+  const bool is_power_of_two_kind = IsPowerOfTwoKind(if_true_, if_false_);
+
+  const intptr_t base = Utils::Minimum(if_true_, if_false_);
+
+  if (if_true_ == base) {
+    // We need to have zero in EDX on true_condition.

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

s/EDX/RDX/

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

Done.

+    true_condition = NegateCondition(true_condition);
+  }
+
+  __ setcc(true_condition, DL);
+
+  if (is_power_of_two_kind) {
+    const intptr_t shift =
+        Utils::ShiftForPowerOfTwo(Utils::Maximum(if_true_, if_false_));
+    __ shll(RDX, Immediate(shift + kSmiTagSize));

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

s/shll/shlq

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

Good catch!

+  } else {
+    ASSERT(kSmiTagSize == 1);
+    __ leaq(RDX, Address(RDX, TIMES_2, base << kSmiTagSize));
+  }
+}
+
+
 LocationSummary* ClosureCallInstr::MakeLocationSummary() const {
   const intptr_t kNumInputs = 0;
   const intptr_t kNumTemps = 1;
   LocationSummary* result =
       new LocationSummary(kNumInputs, kNumTemps, LocationSummary::kCall);
   result->set_out(Location::RegisterLocation(RAX));
   result->set_temp(0, Location::RegisterLocation(R10));  // Arg. descriptor.
   return result;
 }
 
@@ skipping 2963 matching lines @@
   }
 
   // We can fall through if the successor is the next block in the list.
   // Otherwise, we need a jump.
   if (!compiler->CanFallThroughTo(successor())) {
     __ jmp(compiler->GetJumpLabel(successor()));
   }
 }
 
 
-static Condition NegateCondition(Condition condition) {
-  switch (condition) {
-    case EQUAL:         return NOT_EQUAL;
-    case NOT_EQUAL:     return EQUAL;
-    case LESS:          return GREATER_EQUAL;
-    case LESS_EQUAL:    return GREATER;
-    case GREATER:       return LESS_EQUAL;
-    case GREATER_EQUAL: return LESS;
-    case BELOW:         return ABOVE_EQUAL;
-    case BELOW_EQUAL:   return ABOVE;
-    case ABOVE:         return BELOW_EQUAL;
-    case ABOVE_EQUAL:   return BELOW;
-    default:
-      OS::Print("Error %d\n", condition);
-      UNIMPLEMENTED();
-      return EQUAL;
-  }
-}
-
-
 void ControlInstruction::EmitBranchOnValue(FlowGraphCompiler* compiler,
                                            bool value) {
   if (value && !compiler->CanFallThroughTo(true_successor())) {
     __ jmp(compiler->GetJumpLabel(true_successor()));
   } else if (!value && !compiler->CanFallThroughTo(false_successor())) {
     __ jmp(compiler->GetJumpLabel(false_successor()));
   }
 }
 
 
@@ skipping 227 matching lines @@
                          PcDescriptors::kOther,
                          locs());
   __ Drop(2);  // Discard type arguments and receiver.
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_X64