Add rotate-right instruction to hydrogen and use it instead of bitwise operations

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 3387 matching lines @@
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(this);
   sce.Process();
 
   EliminateRedundantBoundsChecks();
   DehoistSimpleArrayIndexComputations();
 
+  EliminateUnusedInstructions();
+
   return true;
 }
 
+void HGraph::EliminateUnusedInstructions() {
+  HPhase phase("H_EliminateUnusedInstructions", this);

[ulan, 2012/10/01 18:15:19]

Maybe I should just do one pass instead of this complex worklist algorithm?

+  ZoneList<HInstruction*> worklist(blocks_.length(), zone());
+  for (int i = 0; i < blocks()->length(); ++i) {
+    HInstruction* instr = blocks()->at(i)->first();
+    while (instr != NULL) {
+      if (instr->UnusedAndSafeToDelete()) {
+        worklist.Add(instr, zone());
+      }
+      instr = instr->next();
+    }
+  }
+
+  while (!worklist.is_empty()) {
+    HInstruction* instr = worklist.RemoveLast();
+    instr->DeleteAndReplaceWith(NULL);
+    for (int i = 0; i < instr->OperandCount(); ++i) {
+      HValue* operand = instr->OperandAt(i);
+      if (operand->IsInstruction() &&
+          HInstruction::cast(operand)->UnusedAndSafeToDelete()) {
+        worklist.Add(HInstruction::cast(operand), zone());
+      }
+    }
+  }
+}
 
 // We try to "factor up" HBoundsCheck instructions towards the root of the
 // dominator tree.
 // For now we handle checks where the index is like "exp + int32value".
 // If in the dominator tree we check "exp + v1" and later (dominated)
 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if
 // v2 > v1 we can use v2 in the 1st check and again remove the second.
 // To do so we keep a dictionary of all checks where the key if the pair
 // "exp, length".
 // The class BoundsCheckKey represents this key.
@@ skipping 4826 matching lines @@
                                                         HValue* index) {
   AddInstruction(new(zone()) HCheckNonSmi(string));
   AddInstruction(HCheckInstanceType::NewIsString(string, zone()));
   HStringLength* length = new(zone()) HStringLength(string);
   AddInstruction(length);
   HInstruction* checked_index =
       AddInstruction(new(zone()) HBoundsCheck(index, length));
   return new(zone()) HStringCharCodeAt(context, string, checked_index);
 }
 
+// Checks if the given shift amounts have form: (sa) and (32 - sa).
+static bool ShiftAmountsAllowReplaceByRotate(HValue* sa,
+                                              HValue* const32_minus_sa) {
+  if (!const32_minus_sa->IsSub()) return false;
+  HSub* sub = HSub::cast(const32_minus_sa);
+  HValue* const32 = sub->left();
+  if (!const32->IsConstant() ||
+      HConstant::cast(const32)->Integer32Value() != 32) {
+    return false;
+  }
+  return (sub->right() == sa);
+}
+
+
+// Checks if the left and the right are shift instructions with the oposite
+// directions that can be replaced by one rotate right instruction or not.
+// Returns the operand and the shift amount for the rotate instruction in the
+// former case.
+bool HGraphBuilder::MatchRotateRight(HValue* left,
+                                     HValue* right,
+                                     HValue** operand,
+                                     HValue** shift_amount) {
+  HShl* shl;
+  HShr* shr;
+  if (left->IsShl() && right->IsShr()) {
+    shl = HShl::cast(left);
+    shr = HShr::cast(right);
+  } else if (left->IsShr() && right->IsShl()) {
+    shl = HShl::cast(right);
+    shr = HShr::cast(left);
+  } else {
+    return false;
+  }
+
+  if (!ShiftAmountsAllowReplaceByRotate(shl->right(), shr->right()) &&
+      !ShiftAmountsAllowReplaceByRotate(shr->right(), shl->right())) {
+    return false;
+  }
+  *operand= shr->left();
+  *shift_amount = shr->right();
+  return true;
+}
+
+
+bool CanBeZero(HValue *right) {
+  if (right->IsConstant()) {
+    HConstant* right_const = HConstant::cast(right);
+    if (right_const->HasInteger32Value() &&
+       (right_const->Integer32Value() & 0x1f) != 0) {
+      return false;
+    }
+  }
+  return true;
+}
+
 
 HInstruction* HGraphBuilder::BuildBinaryOperation(BinaryOperation* expr,
                                                   HValue* left,
                                                   HValue* right) {
   HValue* context = environment()->LookupContext();
   TypeInfo info = oracle()->BinaryType(expr);
   if (info.IsUninitialized()) {
     AddInstruction(new(zone()) HSoftDeoptimize);
     current_block()->MarkAsDeoptimizing();
     info = TypeInfo::Unknown();
@@ skipping 18 matching lines @@
       instr = HMul::NewHMul(zone(), context, left, right);
       break;
     case Token::MOD:
       instr = HMod::NewHMod(zone(), context, left, right);
       break;
     case Token::DIV:
       instr = HDiv::NewHDiv(zone(), context, left, right);
       break;
     case Token::BIT_XOR:
     case Token::BIT_AND:
-    case Token::BIT_OR:
       instr = HBitwise::NewHBitwise(zone(), expr->op(), context, left, right);
       break;
+    case Token::BIT_OR: {
+      HValue* operand, *shift_amount;
+      if (info.IsInteger32() &&
+          MatchRotateRight(left, right, &operand, &shift_amount)) {
+        instr = new(zone()) HRor(context, operand, shift_amount);
+      } else {
+        instr = HBitwise::NewHBitwise(zone(), expr->op(), context, left, right);
+      }
+      break;
+    }
     case Token::SAR:
       instr = HSar::NewHSar(zone(), context, left, right);
       break;
     case Token::SHR:
       instr = HShr::NewHShr(zone(), context, left, right);
-      if (FLAG_opt_safe_uint32_operations && instr->IsShr()) {
-        bool can_be_shift_by_zero = true;
-        if (right->IsConstant()) {
-          HConstant* right_const = HConstant::cast(right);
-          if (right_const->HasInteger32Value() &&
-              (right_const->Integer32Value() & 0x1f) != 0) {
-            can_be_shift_by_zero = false;
-          }
-        }
-
-        if (can_be_shift_by_zero) graph()->RecordUint32Instruction(instr);
+      if (FLAG_opt_safe_uint32_operations && instr->IsShr() &&
+          CanBeZero(right)) {
+        graph()->RecordUint32Instruction(instr);
       }
       break;
     case Token::SHL:
       instr = HShl::NewHShl(zone(), context, left, right);
       break;
     default:
       UNREACHABLE();
   }
 
   // If we hit an uninitialized binary op stub we will get type info
@@ skipping 1659 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal