v8::internal::HRangeAnalysisPhase Class Reference

#include <hydrogen-range-analysis.h>

Inheritance diagram for v8::internal::HRangeAnalysisPhase:

Collaboration diagram for v8::internal::HRangeAnalysisPhase:

Public Member Functions
	HRangeAnalysisPhase (HGraph *graph)
void	Run ()
Public Member Functions inherited from v8::internal::HPhase
	HPhase (const char *name, HGraph *graph)
	~HPhase ()

Private Member Functions
void	TraceRange (const char *msg,...)
void	InferControlFlowRange (HCompareNumericAndBranch *test, HBasicBlock *dest)
void	UpdateControlFlowRange (Token::Value op, HValue *value, HValue *other)
void	InferRange (HValue *value)
void	RollBackTo (int index)
void	AddRange (HValue *value, Range *range)
void	AddToWorklist (HValue *value)
void	PropagateMinusZeroChecks (HValue *value)
void	PoisonRanges ()
	DISALLOW_COPY_AND_ASSIGN (HRangeAnalysisPhase)

Private Attributes
ZoneList< HValue * >	changed_ranges_
BitVector	in_worklist_
ZoneList< HValue * >	worklist_

Additional Inherited Members
Protected Member Functions inherited from v8::internal::HPhase
HGraph *	graph () const

Detailed Description

Definition at line 14 of file hydrogen-range-analysis.h.

Constructor & Destructor Documentation

HRangeAnalysisPhase()

v8::internal::HRangeAnalysisPhase::HRangeAnalysisPhase ( HGraph *  graph )

inlineexplicit

Definition at line 16 of file hydrogen-range-analysis.h.

      : HPhase("H_Range analysis", graph), changed_ranges_(16, zone()),
        in_worklist_(graph->GetMaximumValueID(), zone()),
        worklist_(32, zone()) {}

Member Function Documentation

AddRange()

void v8::internal::HRangeAnalysisPhase::AddRange ( HValue *  value, Range *  range  )

private

Definition at line 195 of file hydrogen-range-analysis.cc.

                                                              {
  Range* original_range = value->range();
  value->AddNewRange(range, graph()->zone());
  changed_ranges_.Add(value, zone());
  Range* new_range = value->range();
  TraceRange("Updated range of %d set to [%d,%d]\n",
             value->id(),
             new_range->lower(),
             new_range->upper());
  if (original_range != NULL) {
    TraceRange("Original range was [%d,%d]\n",
               original_range->lower(),
               original_range->upper());
  }
  TraceRange("New information was [%d,%d]\n",
             range->lower(),
             range->upper());
}

References v8::internal::HValue::AddNewRange(), changed_ranges_, v8::internal::HPhase::graph(), v8::internal::HValue::id(), NULL, v8::internal::HValue::range(), and TraceRange().

Referenced by UpdateControlFlowRange().

Here is the call graph for this function:

Here is the caller graph for this function:

AddToWorklist()

void v8::internal::HRangeAnalysisPhase::AddToWorklist ( HValue *  value )

inlineprivate

Definition at line 31 of file hydrogen-range-analysis.h.

                                    {
    if (in_worklist_.Contains(value->id())) return;
    in_worklist_.Add(value->id());
    worklist_.Add(value, zone());
  }

References v8::internal::BitVector::Add(), v8::internal::BitVector::Contains(), v8::internal::HValue::id(), in_worklist_, and worklist_.

Referenced by PropagateMinusZeroChecks().

Here is the call graph for this function:

Here is the caller graph for this function:

DISALLOW_COPY_AND_ASSIGN()

v8::internal::HRangeAnalysisPhase::DISALLOW_COPY_AND_ASSIGN ( HRangeAnalysisPhase  )

private

InferControlFlowRange()

void v8::internal::HRangeAnalysisPhase::InferControlFlowRange ( HCompareNumericAndBranch *  test, HBasicBlock *  dest  )

private

Definition at line 122 of file hydrogen-range-analysis.cc.

                                                                   {
  DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
  if (test->representation().IsSmiOrInteger32()) {
    Token::Value op = test->token();
    if (test->SecondSuccessor() == dest) {
      op = Token::NegateCompareOp(op);
    }
    Token::Value inverted_op = Token::ReverseCompareOp(op);
    UpdateControlFlowRange(op, test->left(), test->right());
    UpdateControlFlowRange(inverted_op, test->right(), test->left());
  }
}

References DCHECK, v8::internal::HControlInstruction::FirstSuccessor(), v8::internal::Representation::IsSmiOrInteger32(), v8::internal::HCompareNumericAndBranch::left(), v8::internal::Token::NegateCompareOp(), v8::internal::HValue::representation(), v8::internal::Token::ReverseCompareOp(), v8::internal::HCompareNumericAndBranch::right(), v8::internal::HControlInstruction::SecondSuccessor(), v8::internal::HCompareNumericAndBranch::token(), and UpdateControlFlowRange().

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

InferRange()

void v8::internal::HRangeAnalysisPhase::InferRange ( HValue *  value )

private

Definition at line 172 of file hydrogen-range-analysis.cc.

                                                  {
  DCHECK(!value->HasRange());
  if (!value->representation().IsNone()) {
    value->ComputeInitialRange(graph()->zone());
    Range* range = value->range();
    TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
               value->id(),
               value->Mnemonic(),
               range->lower(),
               range->upper());
  }
}

References v8::internal::HValue::ComputeInitialRange(), DCHECK, v8::internal::HPhase::graph(), v8::internal::HValue::HasRange(), v8::internal::HValue::id(), v8::internal::Representation::IsNone(), v8::internal::HValue::Mnemonic(), v8::internal::HValue::range(), v8::internal::HValue::representation(), and TraceRange().

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

PoisonRanges()

void v8::internal::HRangeAnalysisPhase::PoisonRanges ( )

private

Definition at line 109 of file hydrogen-range-analysis.cc.

                                       {
#ifdef DEBUG
  for (int i = 0; i < graph()->blocks()->length(); ++i) {
    HBasicBlock* block = graph()->blocks()->at(i);
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      HInstruction* instr = it.Current();
      if (instr->HasRange()) instr->PoisonRange();
    }
  }
#endif
}

References v8::internal::HPhase::graph(), and v8::internal::HValue::HasRange().

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

PropagateMinusZeroChecks()

void v8::internal::HRangeAnalysisPhase::PropagateMinusZeroChecks ( HValue *  value )

private

Definition at line 215 of file hydrogen-range-analysis.cc.

                                                                {
  DCHECK(worklist_.is_empty());
  DCHECK(in_worklist_.IsEmpty());
 
  AddToWorklist(value);
  while (!worklist_.is_empty()) {
    value = worklist_.RemoveLast();
 
    if (value->IsPhi()) {
      // For phis, we must propagate the check to all of its inputs.
      HPhi* phi = HPhi::cast(value);
      for (int i = 0; i < phi->OperandCount(); ++i) {
        AddToWorklist(phi->OperandAt(i));
      }
    } else if (value->IsUnaryMathOperation()) {
      HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
      if (instr->representation().IsSmiOrInteger32() &&
          !instr->value()->representation().Equals(instr->representation())) {
        if (instr->value()->range() == NULL ||
            instr->value()->range()->CanBeMinusZero()) {
          instr->SetFlag(HValue::kBailoutOnMinusZero);
        }
      }
      if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
          instr->representation().Equals(
              instr->RequiredInputRepresentation(0))) {
        AddToWorklist(instr->value());
      }
    } else if (value->IsChange()) {
      HChange* instr = HChange::cast(value);
      if (!instr->from().IsSmiOrInteger32() &&
          !instr->CanTruncateToInt32() &&
          (instr->value()->range() == NULL ||
           instr->value()->range()->CanBeMinusZero())) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
      }
    } else if (value->IsForceRepresentation()) {
      HForceRepresentation* instr = HForceRepresentation::cast(value);
      AddToWorklist(instr->value());
    } else if (value->IsMod()) {
      HMod* instr = HMod::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
        AddToWorklist(instr->left());
      }
    } else if (value->IsDiv() || value->IsMul()) {
      HBinaryOperation* instr = HBinaryOperation::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
      }
      AddToWorklist(instr->right());
      AddToWorklist(instr->left());
    } else if (value->IsMathFloorOfDiv()) {
      HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
      instr->SetFlag(HValue::kBailoutOnMinusZero);
    } else if (value->IsAdd() || value->IsSub()) {
      HBinaryOperation* instr = HBinaryOperation::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        // Propagate to the left argument. If the left argument cannot be -0,
        // then the result of the add/sub operation cannot be either.
        AddToWorklist(instr->left());
      }
    } else if (value->IsMathMinMax()) {
      HMathMinMax* instr = HMathMinMax::cast(value);
      AddToWorklist(instr->right());
      AddToWorklist(instr->left());
    }
  }
 
  in_worklist_.Clear();
  DCHECK(in_worklist_.IsEmpty());
  DCHECK(worklist_.is_empty());
}

References AddToWorklist(), v8::internal::HValue::cast(), v8::internal::BitVector::Clear(), DCHECK, in_worklist_, v8::internal::BitVector::IsEmpty(), v8::internal::HValue::IsPhi(), v8::internal::HValue::kBailoutOnMinusZero, v8::internal::HBinaryOperation::left(), NULL, v8::internal::HValue::range(), v8::internal::HBinaryOperation::right(), v8::internal::HValue::SetFlag(), and worklist_.

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

RollBackTo()

void v8::internal::HRangeAnalysisPhase::RollBackTo ( int  index )

private

Definition at line 186 of file hydrogen-range-analysis.cc.

                                              {
  DCHECK(index <= changed_ranges_.length());
  for (int i = index; i < changed_ranges_.length(); ++i) {
    changed_ranges_[i]->RemoveLastAddedRange();
  }
  changed_ranges_.Rewind(index);
}

References changed_ranges_, and DCHECK.

Referenced by Run().

Here is the caller graph for this function:

Run()

void v8::internal::HRangeAnalysisPhase::Run

(

)

Definition at line 35 of file hydrogen-range-analysis.cc.

                              {
  HBasicBlock* block(graph()->entry_block());
  ZoneList<Pending> stack(graph()->blocks()->length(), zone());
  while (block != NULL) {
    TraceRange("Analyzing block B%d\n", block->block_id());
 
    // Infer range based on control flow.
    if (block->predecessors()->length() == 1) {
      HBasicBlock* pred = block->predecessors()->first();
      if (pred->end()->IsCompareNumericAndBranch()) {
        InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
                              block);
      }
    }
 
    // Process phi instructions.
    for (int i = 0; i < block->phis()->length(); ++i) {
      HPhi* phi = block->phis()->at(i);
      InferRange(phi);
    }
 
    // Go through all instructions of the current block.
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      HValue* value = it.Current();
      InferRange(value);
 
      // Compute the bailout-on-minus-zero flag.
      if (value->IsChange()) {
        HChange* instr = HChange::cast(value);
        // Propagate flags for negative zero checks upwards from conversions
        // int32-to-tagged and int32-to-double.
        Representation from = instr->value()->representation();
        DCHECK(from.Equals(instr->from()));
        if (from.IsSmiOrInteger32()) {
          DCHECK(instr->to().IsTagged() ||
                instr->to().IsDouble() ||
                instr->to().IsSmiOrInteger32());
          PropagateMinusZeroChecks(instr->value());
        }
      } else if (value->IsCompareMinusZeroAndBranch()) {
        HCompareMinusZeroAndBranch* instr =
            HCompareMinusZeroAndBranch::cast(value);
        if (instr->value()->representation().IsSmiOrInteger32()) {
          PropagateMinusZeroChecks(instr->value());
        }
      }
    }
 
    // Continue analysis in all dominated blocks.
    const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
    if (!dominated_blocks->is_empty()) {
      // Continue with first dominated block, and push the
      // remaining blocks on the stack (in reverse order).
      int last_changed_range = changed_ranges_.length();
      for (int i = dominated_blocks->length() - 1; i > 0; --i) {
        stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
      }
      block = dominated_blocks->at(0);
    } else if (!stack.is_empty()) {
      // Pop next pending block from stack.
      Pending pending = stack.RemoveLast();
      RollBackTo(pending.last_changed_range());
      block = pending.block();
    } else {
      // All blocks done.
      block = NULL;
    }
  }
 
  // The ranges are not valid anymore due to SSI vs. SSA!
  PoisonRanges();
}

References v8::internal::List< T, AllocationPolicy >::Add(), v8::internal::List< T, AllocationPolicy >::at(), v8::internal::Pending::block(), v8::internal::HValue::cast(), changed_ranges_, DCHECK, v8::internal::Representation::Equals(), v8::internal::HPhase::graph(), InferControlFlowRange(), InferRange(), v8::internal::Representation::IsSmiOrInteger32(), v8::internal::Pending::last_changed_range(), NULL, PoisonRanges(), PropagateMinusZeroChecks(), RollBackTo(), and TraceRange().

Here is the call graph for this function:

TraceRange()

void v8::internal::HRangeAnalysisPhase::TraceRange ( const char *  msg,   ...  )

private

Definition at line 25 of file hydrogen-range-analysis.cc.

                                                         {
  if (FLAG_trace_range) {
    va_list arguments;
    va_start(arguments, msg);
    base::OS::VPrint(msg, arguments);
    va_end(arguments);
  }
}

References v8::base::OS::VPrint().

Referenced by AddRange(), InferRange(), Run(), and UpdateControlFlowRange().

Here is the call graph for this function:

Here is the caller graph for this function:

UpdateControlFlowRange()

void v8::internal::HRangeAnalysisPhase::UpdateControlFlowRange ( Token::Value  op, HValue *  value, HValue *  other  )

private

Definition at line 139 of file hydrogen-range-analysis.cc.

                                                                {
  Range temp_range;
  Range* range = other->range() != NULL ? other->range() : &temp_range;
  Range* new_range = NULL;
 
  TraceRange("Control flow range infer %d %s %d\n",
             value->id(),
             Token::Name(op),
             other->id());
 
  if (op == Token::EQ || op == Token::EQ_STRICT) {
    // The same range has to apply for value.
    new_range = range->Copy(graph()->zone());
  } else if (op == Token::LT || op == Token::LTE) {
    new_range = range->CopyClearLower(graph()->zone());
    if (op == Token::LT) {
      new_range->AddConstant(-1);
    }
  } else if (op == Token::GT || op == Token::GTE) {
    new_range = range->CopyClearUpper(graph()->zone());
    if (op == Token::GT) {
      new_range->AddConstant(1);
    }
  }
 
  if (new_range != NULL && !new_range->IsMostGeneric()) {
    AddRange(value, new_range);
  }
}

References AddRange(), v8::internal::EQ, v8::internal::HPhase::graph(), v8::internal::HValue::id(), v8::internal::Token::Name(), NULL, v8::internal::HValue::range(), and TraceRange().

Referenced by InferControlFlowRange().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

changed_ranges_

ZoneList<HValue*> v8::internal::HRangeAnalysisPhase::changed_ranges_

private

Definition at line 39 of file hydrogen-range-analysis.h.

Referenced by AddRange(), RollBackTo(), and Run().

in_worklist_

BitVector v8::internal::HRangeAnalysisPhase::in_worklist_

private

Definition at line 41 of file hydrogen-range-analysis.h.

Referenced by AddToWorklist(), and PropagateMinusZeroChecks().

worklist_

ZoneList<HValue*> v8::internal::HRangeAnalysisPhase::worklist_

private

Definition at line 42 of file hydrogen-range-analysis.h.

Referenced by AddToWorklist(), and PropagateMinusZeroChecks().

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/hydrogen-range-analysis.h
• /mnt/V8SourceCode/src/hydrogen-range-analysis.cc