Crankshaft: Recognize (i >>> 0) === i for integer32 inputs and replace

src/hydrogen.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 10023 matching lines @@
 Representation HOptimizedGraphBuilder::ToRepresentation(TypeInfo info) {
   if (info.IsUninitialized()) return Representation::None();
   if (info.IsSmi()) return Representation::Integer32();
   if (info.IsInteger32()) return Representation::Integer32();
   if (info.IsDouble()) return Representation::Double();
   if (info.IsNumber()) return Representation::Double();
   return Representation::Tagged();
 }
 
 
+void HOptimizedGraphBuilder::HandleTripleShiftZeroCompare(
+    CompareOperation* expr,
+    HValue* input) {
+  // (i >>> 0) === i is transformed to i >= 0.
+  // (i >>> 0) !== i is transformed to i < 0.
+  Token::Value op = (expr->op() == Token::EQ_STRICT) ? Token::GTE : Token::LT;
+  HCompareIDAndBranch* compare =
+      new(zone()) HCompareIDAndBranch(input, graph()->GetConstant0(), op);
+  compare->set_observed_input_representation(Representation::Integer32(),

[Jakob Kummerow, 2013/04/23 11:09:23]

Manually setting observed input representations is a hack. Please harvest i's
representation from the >>> operation instead.

+                                             Representation::Integer32());
+  compare->set_position(expr->position());
+  return ast_context()->ReturnControl(compare, expr->id());
+}
+
+
 void HOptimizedGraphBuilder::HandleLiteralCompareTypeof(CompareOperation* expr,
                                                         HTypeof* typeof_expr,
                                                         Handle<String> check) {
   // Note: The HTypeof itself is removed during canonicalization, if possible.
   HValue* value = typeof_expr->value();
   HTypeofIsAndBranch* instr = new(zone()) HTypeofIsAndBranch(value, check);
   instr->set_position(expr->position());
   return ast_context()->ReturnControl(instr, expr->id());
 }
 
 
 static bool MatchLiteralCompareNil(HValue* left,
                                    Token::Value op,
                                    HValue* right,
                                    Handle<Object> nil,
                                    HValue** expr) {
   if (left->IsConstant() &&
       HConstant::cast(left)->handle().is_identical_to(nil) &&
       Token::IsEqualityOp(op)) {
     *expr = right;
     return true;
   }
   return false;
 }
 
 
+// Recognize the pattern (i >>> 0) !== i.
+static bool MatchTripleShiftZeroCompare(HValue* left,
+                                        Token::Value op,
+                                        HValue* right,
+                                        HValue** input) {
+  if (!right->representation().IsInteger32()) return false;

[Jakob Kummerow, 2013/04/23 11:09:23]

You can't rely on representations at graph construction time. For most
instructions, they're not set at all, and they can change later during the
representation inference phase.

I think replacement operations like this belong in the Canonicalization pass.

+  if (!left->IsShr()) return false;
+  HShr* shr =  HShr::cast(left);
+  if (right != shr->left()) return false;
+  if (!shr->right()->IsConstant()) return false;
+  HConstant* shiftOperand = HConstant::cast(shr->right());
+  if (*(shiftOperand->handle()) != Smi::FromInt(0)) return false;
+  *input = right;
+  return true;
+}
+
+
+static bool IsTripleShiftZeroCompare(HValue* left,
+                                     Token::Value op,
+                                     HValue* right,
+                                     HValue** input) {
+  if (!Token::IsStrictOp(op)) return false;
+  return MatchTripleShiftZeroCompare(left, op, right, input) ||
+      MatchTripleShiftZeroCompare(right, op, left, input);
+}
+
+
+
 static bool MatchLiteralCompareTypeof(HValue* left,
                                       Token::Value op,
                                       HValue* right,
                                       HTypeof** typeof_expr,
                                       Handle<String>* check) {
   if (left->IsTypeof() &&
       Token::IsEqualityOp(op) &&
       right->IsConstant() &&
       HConstant::cast(right)->handle()->IsString()) {
     *typeof_expr = HTypeof::cast(left);
@@ skipping 69 matching lines @@
   HValue* right = Pop();
   HValue* left = Pop();
   Token::Value op = expr->op();
 
   HTypeof* typeof_expr = NULL;
   Handle<String> check;
   if (IsLiteralCompareTypeof(left, op, right, &typeof_expr, &check)) {
     return HandleLiteralCompareTypeof(expr, typeof_expr, check);
   }
   HValue* sub_expr = NULL;
+  if (IsTripleShiftZeroCompare(left, op, right, &sub_expr)) {
+    return HandleTripleShiftZeroCompare(expr, sub_expr);
+  }
   Factory* f = isolate()->factory();
   if (IsLiteralCompareNil(left, op, right, f->undefined_value(), &sub_expr)) {
     return HandleLiteralCompareNil(expr, sub_expr, kUndefinedValue);
   }
   if (IsLiteralCompareNil(left, op, right, f->null_value(), &sub_expr)) {
     return HandleLiteralCompareNil(expr, sub_expr, kNullValue);
   }
   if (IsLiteralCompareBool(left, op, right)) {
     HCompareObjectEqAndBranch* result =
         new(zone()) HCompareObjectEqAndBranch(left, right);
@@ skipping 1703 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal