Infrastructure classes for evaluating numeric relations between values.

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 387 matching lines @@
     return false;
   }
 }
 
 
 bool HValue::TestDominanceUsingProcessedFlag(HValue* dominator,
                                              HValue* dominated) {
   if (dominator->block() != dominated->block()) {
     return dominator->block()->Dominates(dominated->block());
   } else {
-    // If both arguments are in the same block we check if "dominator" has
-    // already been processed or if it is a phi: if yes it dominates the other.
-    return dominator->CheckFlag(kIDefsProcessingDone) || dominator->IsPhi();
+    // If both arguments are in the same block we check if dominator is a phi
+    // or if dominated has not already been processed: in either case we know
+    // that dominator precedes dominated.
+    return dominator->IsPhi() || !dominated->CheckFlag(kIDefsProcessingDone);
   }
 }
 
 
 bool HValue::IsDefinedAfter(HBasicBlock* other) const {
   return block()->block_id() > other->block_id();
 }
 
 
 HUseListNode* HUseListNode::tail() {
@@ skipping 96 matching lines @@
   switch (opcode()) {
 #define MAKE_CASE(type) case k##type: return #type;
     HYDROGEN_CONCRETE_INSTRUCTION_LIST(MAKE_CASE)
 #undef MAKE_CASE
     case kPhi: return "Phi";
     default: return "";
   }
 }
 
 
+bool HValue::IsInteger32Constant() {
+  return IsConstant() && HConstant::cast(this)->HasInteger32Value();
+}
+
+
+int32_t HValue::GetInteger32Constant() {
+  return HConstant::cast(this)->Integer32Value();
+}
+
+
 void HValue::SetOperandAt(int index, HValue* value) {
   RegisterUse(index, value);
   InternalSetOperandAt(index, value);
 }
 
 
 void HValue::DeleteAndReplaceWith(HValue* other) {
   // We replace all uses first, so Delete can assert that there are none.
   if (other != NULL) ReplaceAllUsesWith(other);
   ASSERT(HasNoUses());
@@ skipping 250 matching lines @@
   }
 
   // Verify that instructions that can be eliminated by GVN have overridden
   // HValue::DataEquals.  The default implementation is UNREACHABLE.  We
   // don't actually care whether DataEquals returns true or false here.
   if (CheckFlag(kUseGVN)) DataEquals(this);
 }
 #endif
 
 
+HNumericConstraint* HNumericConstraint::AddToGraph(
+    HValue* constrained_value,
+    NumericRelation relation,
+    HValue* related_value,
+    HInstruction* insertion_point) {
+  if (insertion_point == NULL) {
+    if (constrained_value->IsInstruction()) {
+      insertion_point = HInstruction::cast(constrained_value);
+    } else if (constrained_value->IsPhi()) {
+      insertion_point = constrained_value->block()->first();
+    } else {
+      UNREACHABLE();
+    }
+  }
+  HNumericConstraint* result =
+      new(insertion_point->block()->zone()) HNumericConstraint(
+          constrained_value, relation, related_value);
+  result->InsertAfter(insertion_point);
+  return result;
+}
+
+
+void HNumericConstraint::PrintDataTo(StringStream* stream) {
+  stream->Add("(");
+  constrained_value()->PrintNameTo(stream);
+  stream->Add(" %s ", relation().Mnemonic());
+  related_value()->PrintNameTo(stream);
+  stream->Add(")");
+}
+
+
 void HDummyUse::PrintDataTo(StringStream* stream) {
   value()->PrintNameTo(stream);
 }
 
 
 void HUnaryCall::PrintDataTo(StringStream* stream) {
   value()->PrintNameTo(stream);
   stream->Add(" ");
   stream->Add("#%d", argument_count());
 }
 
 
 void HBinaryCall::PrintDataTo(StringStream* stream) {
   first()->PrintNameTo(stream);
   stream->Add(" ");
   second()->PrintNameTo(stream);
   stream->Add(" ");
   stream->Add("#%d", argument_count());
 }
 
 
+void HBoundsCheck::AddInformativeDefinitions() {

[Jakob Kummerow, 2013/02/13 13:20:56]

Please add a comment here:
  // TODO(mmassi): Executing this code during AddInformativeDefinitions
  // is a hack. Move it to some other HPhase.

+  if (index()->IsRelationTrue(NumericRelation::Ge(),
+                              block()->graph()->GetConstant0()) &&
+      index()->IsRelationTrue(NumericRelation::Lt(), length())) {
+    set_skip_check(true);
+  }
+}
+
+
+bool HBoundsCheck::IsRelationTrueInternal(NumericRelation relation,
+                                          HValue* related_value) {
+  if (related_value == length()) {
+    // A HBoundsCheck is smaller than the length it compared against.
+    return NumericRelation::Lt().Implies(relation);
+  } else if (related_value == block()->graph()->GetConstant0()) {
+    // A HBoundsCheck is greater than or equal to zero.
+    return NumericRelation::Ge().Implies(relation);
+  } else {
+    return false;
+  }
+}
+
+
 void HBoundsCheck::PrintDataTo(StringStream* stream) {
   index()->PrintNameTo(stream);
   stream->Add(" ");
   length()->PrintNameTo(stream);
+  if (skip_check()) {
+    stream->Add(" [DISABLED]");
+  }
 }
 
 
 void HBoundsCheck::InferRepresentation(HInferRepresentation* h_infer) {
   ASSERT(CheckFlag(kFlexibleRepresentation));
   Representation r;
   if (key_mode_ == DONT_ALLOW_SMI_KEY ||
       !length()->representation().IsTagged()) {
     r = Representation::Integer32();
   } else if (index()->representation().IsTagged() ||
@@ skipping 636 matching lines @@
     if (!right()->range()->CanBeZero()) {
       ClearFlag(HValue::kCanBeDivByZero);
     }
     return result;
   } else {
     return HValue::InferRange(zone);
   }
 }
 
 
+void HPhi::AddInformativeDefinitions() {
+  if (OperandCount() == 2) {
+    for (int operand_index = 0; operand_index < 2; operand_index++) {
+      int other_operand_index = (operand_index + 1) % 2;
+
+      // Add an idef that "discards" the OSR entry block branch.
+      if (OperandAt(operand_index)->block()->is_osr_entry()) {
+        HNumericConstraint::AddToGraph(
+              this, NumericRelation::Eq(), OperandAt(other_operand_index));

[Jakob Kummerow, 2013/02/13 13:20:56]

nit: 4 spaces indentation is enough

+      }
+
+      static NumericRelation relations[] = {
+        NumericRelation::Ge(),
+        NumericRelation::Le()
+      };
+
+      // Check if this phi is an induction variable.

[Jakob Kummerow, 2013/02/13 13:20:56]

Please extend this comment to convey the reasoning behind the code:
      // Check if this phi is an induction variable. If, e.g., we know that
      // its first input is greater than the phi itself, then that must be
      // the back edge, and the phi is always greater than its second input.

+      for (int relation_index = 0; relation_index < 2; relation_index++) {
+        if (OperandAt(operand_index)->IsRelationTrue(relations[relation_index],
+                                                     this)) {
+          HNumericConstraint::AddToGraph(this,
+                                         relations[relation_index],
+                                         OperandAt(other_operand_index));
+        }
+      }
+    }
+  }
+}
+
+
 Range* HMathMinMax::InferRange(Zone* zone) {
   if (representation().IsInteger32()) {
     Range* a = left()->range();
     Range* b = right()->range();
     Range* res = a->Copy(zone);
     if (operation_ == kMathMax) {
       res->CombinedMax(b);
     } else {
       ASSERT(operation_ == kMathMin);
       res->CombinedMin(b);
@@ skipping 393 matching lines @@
         result->Sar(c->Integer32Value());
         result->set_can_be_minus_zero(false);
         return result;
       }
     }
   }
   return HValue::InferRange(zone);
 }
 
 
+

[Jakob Kummerow, 2013/02/13 13:20:56]

nit: unneeded whitespace

 Range* HShl::InferRange(Zone* zone) {
   if (right()->IsConstant()) {
     HConstant* c = HConstant::cast(right());
     if (c->HasInteger32Value()) {
       Range* result = (left()->range() != NULL)
           ? left()->range()->Copy(zone)
           : new(zone) Range();
       result->Shl(c->Integer32Value());
       result->set_can_be_minus_zero(false);
       return result;
@@ skipping 28 matching lines @@
 }
 
 
 void HStringCompareAndBranch::PrintDataTo(StringStream* stream) {
   stream->Add(Token::Name(token()));
   stream->Add(" ");
   HControlInstruction::PrintDataTo(stream);
 }
 
 
+void HCompareIDAndBranch::AddInformativeDefinitions() {
+  NumericRelation r = NumericRelation::FromToken(token());
+  if (r.IsNone()) return;
+
+  HNumericConstraint::AddToGraph(left(), r, right(), SuccessorAt(0)->first());
+  HNumericConstraint::AddToGraph(
+        left(), r.Negated(), right(), SuccessorAt(1)->first());
+}
+
+
 void HCompareIDAndBranch::PrintDataTo(StringStream* stream) {
   stream->Add(Token::Name(token()));
   stream->Add(" ");
   left()->PrintNameTo(stream);
   stream->Add(" ");
   right()->PrintNameTo(stream);
   HControlInstruction::PrintDataTo(stream);
 }
 
 
@@ skipping 992 matching lines @@
 
 
 void HCheckFunction::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal