Use integer division in a certain case.

src/hydrogen-instructions.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 297 matching lines @@
 }
 
 
 int HValue::UseCount() const {
   int count = 0;
   for (HUseIterator it(uses()); !it.Done(); it.Advance()) ++count;
   return count;
 }
 
 
+int HValue::UseCountIgnoringInputsRequiringNone() const {
+  int count = 0;
+  for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
+    Representation req = it.value()->RequiredInputRepresentation(it.index());
+    if (!req.IsNone()) count++;
+  }
+  return count;
+}
+
+
 HUseListNode* HValue::RemoveUse(HValue* value, int index) {
   HUseListNode* previous = NULL;
   HUseListNode* current = use_list_;
   while (current != NULL) {
     if (current->value() == value && current->index() == index) {
       if (previous == NULL) {
         use_list_ = current->tail();
       } else {
         previous->set_tail(current->tail());
       }
@@ skipping 767 matching lines @@
 
 
 Range* HValue::InferRange(Zone* zone) {
   // Untagged integer32 cannot be -0, all other representations can.
   Range* result = new(zone) Range();
   result->set_can_be_minus_zero(!representation().IsInteger32());
   return result;
 }
 
 
+#if defined(V8_TARGET_ARCH_IA32) || defined(V8_TARGET_ARCH_X64)
+
+// Return an integer value or NULL, which may involve skipping over a
+// representation change
+static HValue* SimplifiedValueForIntDiv(HValue* value) {
+  if (value->representation().IsInteger32()) {
+    return value;
+  } else if (value->IsConstant() &&
+      HConstant::cast(value)->HasInteger32Value()) {
+    return value;
+  } else if (value->IsChange() &&
+      HChange::cast(value)->from().IsInteger32()) {
+    return HChange::cast(value)->value();
+  }
+  return NULL;
+}
+
+
+// Insert an integer constant into the graph when given a non-integer constant
+static HValue* EnsureIntegerConstantForIntDiv(HValue* value,
+                                              HInstruction* insertBefore) {
+  if (value->IsConstant() && !value->representation().IsInteger32()) {
+    ASSERT(HConstant::cast(value)->HasInteger32Value());
+    HConstant* constant = HConstant::cast(value)->CopyToRepresentation(
+      Representation::Integer32(), insertBefore->block()->zone());
+    constant->InsertBefore(insertBefore);
+    return constant;
+  }
+  return value;
+}
+
+
+// Try to replace the division of a non-negative integer by a positive integer
+// that is then truncated to an integer with an integer division instruction.
+// This gives a 2x speedup over using double division. Return NULL on failure.
+static HDiv* MaybeConvertToIntDiv(HChange* change, Zone* zone) {
+  if (change->value()->IsDiv() &&

[Vyacheslav Egorov (Google), 2012/07/30 12:01:44]

I am a little bit uncomfortable that we apply this optimization to any d to i
change, even those that are not truncating. 

Changes can be inserted optimistically and they deopt when they see a value not
representable as integer. 

So it seems suspicious that such optimistic change can be removed by an opt.

[Evan Wallace, 2012/07/30 16:43:13]

These aren't the only conditions that trigger this optimization. It must also be
the case that both operands are integers, the dividend is non-negative, and the
divisor is positive. This ensures that the result of the division can always be
representable as an integer and that the deopt will never be hit. For example,
with the following HIR:

d3 = Div i1, i2
i4 = Change d to i d3

The preconditions are:
- i1 is an int32 in range [a, b] where 0 <= a <= b <= kMaxInt
- i2 is an int32 in range [c, d] where 1 <= c <= d <= kMaxInt

Thus the range of the result is [a / d, b / c] which can always be safely
truncated to int32 range since:
- 0 <= a / d <= a
- 0 <= b / c <= b
- a / d <= b / c

[Vyacheslav Egorov (Google), 2012/07/30 16:59:26]

I don't dispute that it can be truncated to int32. 
My concern is that it can necessarily be represented as int32 e.g. 1/2 can be
truncated to int32 but it is not representable in int32.

Normal Change d -> i is not truncating, it will deopt on non-integer values
(which corresponds to non-zero remainder).

What do you think about limiting this optimization to truncating Change
instructions?

I suspect we can mark store into int32/int16/int8 array (and associated Change)
as truncating. 

[Evan Wallace, 2012/07/30 19:35:43]

I did not realize normal double to integer representation changes are not
truncating. I will add a check for that flag on "change".

From what I can tell, if the optimization is only applied when the division has
a use count of 1 then marking storing into a typed array as truncating won't
have any effect since "x[0] = 0xFF / (x[0] + 1)" will always generate a simulate
that pushes the division.

What conditions would be necessary to apply this substitution in that case?
Would it be valid to apply this substitution if there are one or more simulate
instructions for which the division is a use but they occur after the change
instruction (instead of before as in your example below)?

+      change->from().IsDouble() &&
+      change->to().IsInteger32()) {
+    HDiv* div = HDiv::cast(change->value());
+
+    // We want to be sure that the use count is 1 for div so we can swap it
+    // out, but there may be other instructions (such as HSimulate) that do
+    // not need the resulting value and so shouldn't stop this optimization
+    if (div->UseCountIgnoringInputsRequiringNone() == 1) {

[Vyacheslav Egorov (Google), 2012/07/30 12:01:44]

I am not sure that your approach to simulates is correct.

First of all simulate does need a resulting value e.g. it can be stored into a
local, so after deopt local will see integer not double.

Secondly, imagine that we have a simulate followed by a map check that ensures
that we actually store into int32 array (and thus we convert to int32) -> if map
check fails simulate we will deopt into an incorrect state with a value
truncated to int32. (Pseudo)HIR to illustrate:

d4 = Div d2, d3 
Simulate push d4
i5 = Change d to i d4
CheckMaps t0
StoreFastKeyedExternalElement t0[i1] = i5

[Evan Wallace, 2012/07/30 16:43:13]

Thanks for pointing this out! I guess I don't understand HSimulate then. I
needed it for the case in my example of updating an element in a typed array
"x[0] = 0xFF / (x[0] + 1)" but that can be done instead by using "x[0] = 0 |
0xFF / (x[0] + 1)", which doesn't generate a HSimulate pointing to the HDiv.
I'll change this to require an absolute use count of 1 instead.

[Vyacheslav Egorov (Google), 2012/07/30 16:59:26]

Simulate is a pseudo-instruction that "simulates" changes that happen with the
state of unoptimized code corresponding to a particular position in optimized
code. It is needed to compute how stack frames would look like for unoptimized
code when we deopt. One can say that simulates delta-encode deoptimization
environments as each simulate describes what observable changes happened to the
state since the previous simulate: what was stored into local variables, what
was pushed to expression stack or how many values were poped from it.  

Uses at simulate describe what unoptimized code will see if deopt happens
between this simulate and the next one.

+      HValue* left = div->left();
+      HValue* right = div->right();
+      HValue* new_left = SimplifiedValueForIntDiv(left);
+      HValue* new_right = SimplifiedValueForIntDiv(right);
+
+      // Only apply this optimization if we know it won't hit any special cases
+      if (new_left != NULL && new_right != NULL &&
+          new_left->range()->lower() >= 0 &&
+          new_right->range()->lower() > 0) {
+        // Change non-integer constants to integer constants
+        new_left = EnsureIntegerConstantForIntDiv(new_left, div);
+        new_right = EnsureIntegerConstantForIntDiv(new_right, div);
+        ASSERT(new_left->representation().IsInteger32());
+        ASSERT(new_right->representation().IsInteger32());
+
+        // Replace this representation change with an integer division
+        HDiv* new_div = new(div->block()->zone()) HDiv(div->context(),
+          new_left, new_right);
+        new_div->AssumeRepresentation(Representation::Integer32());
+        new_div->InsertBefore(div);
+        change->DeleteAndReplaceWith(new_div);
+
+        // Delete unused instructions
+        div->DeleteAndReplaceWith(new_div);
+        if (left->HasNoUses()) left->DeleteAndReplaceWith(NULL);
+        if (right->HasNoUses()) right->DeleteAndReplaceWith(NULL);
+
+        // Tell codegen not to emit code to check for a non-zero remainder.
+        // Codegen can't use CheckUsesForFlag(kTruncatingToInt32) because
+        // that flag is on the HChange instruction which is now deleted.
+        new_div->SetFlag(HValue::kWillTruncateToInt32);
+
+        // Make sure all new values have ranges
+        if (!new_left->HasRange()) new_left->ComputeInitialRange(zone);
+        if (!new_right->HasRange()) new_right->ComputeInitialRange(zone);
+        new_div->ComputeInitialRange(zone);
+        return new_div;
+      }
+    }
+  }
+  return NULL;
+}
+
+#endif
+
+
 Range* HChange::InferRange(Zone* zone) {
+#if defined(V8_TARGET_ARCH_IA32) || defined(V8_TARGET_ARCH_X64)
+  HDiv *div = MaybeConvertToIntDiv(this, zone);
+  if (div != NULL) {
+    return div->range();
+  }
+#endif
+
   Range* input_range = value()->range();
   if (from().IsInteger32() &&
       to().IsTagged() &&
       input_range != NULL && input_range->IsInSmiRange()) {
     set_type(HType::Smi());
   }
   Range* result = (input_range != NULL)
       ? input_range->Copy(zone)
       : HValue::InferRange(zone);
   if (to().IsInteger32()) result->set_can_be_minus_zero(false);
@@ skipping 86 matching lines @@
     if (left()->range()->CanBeMinusZero()) {
       result->set_can_be_minus_zero(true);
     }
 
     if (left()->range()->CanBeZero() && right()->range()->CanBeNegative()) {
       result->set_can_be_minus_zero(true);
     }
 
     if (right()->range()->Includes(-1) && left()->range()->Includes(kMinInt)) {
       SetFlag(HValue::kCanOverflow);
+    } else {
+      ClearFlag(HValue::kCanOverflow);
     }
 
     if (!right()->range()->CanBeZero()) {
       ClearFlag(HValue::kCanBeDivByZero);
     }
+
+    // An exact range can be inferred for division with integer operands
+    if (left()->representation().IsInteger32() &&
+        right()->representation().IsInteger32() &&
+        left()->range()->lower() >= 0 &&
+        right()->range()->lower() > 0) {
+      Range limits(left()->range()->lower() / right()->range()->upper(),
+        left()->range()->upper() / right()->range()->lower());
+      result->Intersect(&limits);
+    }
     return result;
   } else {
     return HValue::InferRange(zone);
   }
 }
 
 
 Range* HMod::InferRange(Zone* zone) {
   if (representation().IsInteger32()) {
     Range* a = left()->range();
@@ skipping 1357 matching lines @@
 
 
 void HCheckPrototypeMaps::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal