LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-environment-liveness.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 88 88 100.0 %
Date: 2017-04-26 Functions: 7 7 100.0 %

          Line data    Source code
       1             : // Copyright 2013 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : 
       6             : #include "src/crankshaft/hydrogen-environment-liveness.h"
       7             : #include "src/objects-inl.h"
       8             : 
       9             : namespace v8 {
      10             : namespace internal {
      11             : 
      12             : 
      13      280033 : HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
      14      280033 :     HGraph* graph)
      15             :     : HPhase("H_Environment liveness analysis", graph),
      16      280033 :       block_count_(graph->blocks()->length()),
      17             :       maximum_environment_size_(graph->maximum_environment_size()),
      18             :       live_at_block_start_(block_count_, zone()),
      19             :       first_simulate_(block_count_, zone()),
      20             :       first_simulate_invalid_for_index_(block_count_, zone()),
      21             :       markers_(maximum_environment_size_, zone()),
      22             :       collect_markers_(true),
      23             :       last_simulate_(NULL),
      24      560066 :       went_live_since_last_simulate_(maximum_environment_size_, zone()) {
      25             :   DCHECK(maximum_environment_size_ > 0);
      26     4599894 :   for (int i = 0; i < block_count_; ++i) {
      27             :     live_at_block_start_.Add(
      28     4319851 :         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
      29             :     first_simulate_.Add(NULL, zone());
      30             :     first_simulate_invalid_for_index_.Add(
      31     4319856 :         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
      32             :   }
      33      280036 : }
      34             : 
      35             : 
      36      486222 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
      37             :     int index, HSimulate* simulate) {
      38             :   int operand_index = simulate->ToOperandIndex(index);
      39      486222 :   if (operand_index == -1) {
      40      486222 :     simulate->AddAssignedValue(index, graph()->GetConstantOptimizedOut());
      41             :   } else {
      42      120975 :     simulate->SetOperandAt(operand_index, graph()->GetConstantOptimizedOut());
      43             :   }
      44      486222 : }
      45             : 
      46             : 
      47     4319848 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
      48     8991822 :     HBasicBlock* block, BitVector* live) {
      49             :   // When a value is live in successor A but dead in B, we must
      50             :   // explicitly zap it in B.
      51     9193481 :   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
      52     4873636 :     HBasicBlock* successor = it.Current();
      53             :     int successor_id = successor->block_id();
      54    10344734 :     BitVector* live_in_successor = live_at_block_start_[successor_id];
      55     4873636 :     if (live_in_successor->Equals(*live)) continue;
      56     4671974 :     for (int i = 0; i < live->length(); ++i) {
      57     2211736 :       if (!live->Contains(i)) continue;
      58      597462 :       if (live_in_successor->Contains(i)) continue;
      59      589670 :       if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
      60             :         continue;
      61             :       }
      62      294764 :       HSimulate* simulate = first_simulate_.at(successor_id);
      63      294764 :       if (simulate == NULL) continue;
      64             :       DCHECK(VerifyClosures(simulate->closure(),
      65             :           block->last_environment()->closure()));
      66      274495 :       ZapEnvironmentSlot(i, simulate);
      67             :     }
      68             :   }
      69     4319851 : }
      70             : 
      71             : 
      72     1275638 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
      73      623167 :     HEnvironmentMarker* marker) {
      74     3826914 :   if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
      75             :   HSimulate* simulate = marker->next_simulate();
      76      411440 :   if (simulate != NULL) {
      77             :     DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
      78      211727 :     ZapEnvironmentSlot(marker->index(), simulate);
      79             :   }
      80             : }
      81             : 
      82             : 
      83     8902815 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
      84     8902815 :     HBasicBlock* block,
      85    18971552 :     BitVector* live) {
      86             :   // Liveness at the end of each block: union of liveness in successors.
      87             :   live->Clear();
      88    18971530 :   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
      89    20137474 :     live->Union(*live_at_block_start_[it.Current()->block_id()]);
      90             :   }
      91     8902788 : }
      92             : 
      93             : 
      94    30685792 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
      95             :     HInstruction* instr,
      96     3766691 :     BitVector* live) {
      97    30685792 :   switch (instr->opcode()) {
      98             :     case HValue::kEnvironmentMarker: {
      99             :       HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
     100     3136804 :       int index = marker->index();
     101     1568402 :       if (!live->Contains(index)) {
     102             :         marker->SetFlag(HValue::kEndsLiveRange);
     103             :       } else {
     104             :         marker->ClearFlag(HValue::kEndsLiveRange);
     105             :       }
     106     8839439 :       if (!went_live_since_last_simulate_.Contains(index)) {
     107     1493781 :         marker->set_next_simulate(last_simulate_);
     108             :       }
     109     1568402 :       if (marker->kind() == HEnvironmentMarker::LOOKUP) {
     110             :         live->Add(index);
     111             :       } else {
     112             :         DCHECK(marker->kind() == HEnvironmentMarker::BIND);
     113             :         live->Remove(index);
     114             :         went_live_since_last_simulate_.Add(index);
     115             :       }
     116     1568402 :       if (collect_markers_) {
     117             :         // Populate |markers_| list during the first pass.
     118     1275636 :         markers_.Add(marker, zone());
     119             :       }
     120             :       break;
     121             :     }
     122             :     case HValue::kLeaveInlined:
     123             :       // No environment values are live at the end of an inlined section.
     124             :       live->Clear();
     125      524031 :       last_simulate_ = NULL;
     126             : 
     127             :       // The following DCHECKs guard the assumption used in case
     128             :       // kEnterInlined below:
     129             :       DCHECK(instr->next()->IsSimulate());
     130             :       DCHECK(instr->next()->next()->IsGoto());
     131             : 
     132      524031 :       break;
     133             :     case HValue::kEnterInlined: {
     134             :       // Those environment values are live that are live at any return
     135             :       // target block. Here we make use of the fact that the end of an
     136             :       // inline sequence always looks like this: HLeaveInlined, HSimulate,
     137             :       // HGoto (to return_target block), with no environment lookups in
     138             :       // between (see DCHECKs above).
     139             :       HEnterInlined* enter = HEnterInlined::cast(instr);
     140             :       live->Clear();
     141      125447 :       for (int i = 0; i < enter->return_targets()->length(); ++i) {
     142      125447 :         int return_id = enter->return_targets()->at(i)->block_id();
     143      250894 :         live->Union(*live_at_block_start_[return_id]);
     144             :       }
     145      105856 :       last_simulate_ = NULL;
     146      105856 :       break;
     147             :     }
     148             :     case HValue::kSimulate:
     149     5104352 :       last_simulate_ = HSimulate::cast(instr);
     150             :       went_live_since_last_simulate_.Clear();
     151             :       break;
     152             :     default:
     153             :       break;
     154             :   }
     155    30685760 : }
     156             : 
     157             : 
     158      280036 : void HEnvironmentLivenessAnalysisPhase::Run() {
     159             :   DCHECK(maximum_environment_size_ > 0);
     160             : 
     161             :   // Main iteration. Compute liveness of environment slots, and store it
     162             :   // for each block until it doesn't change any more. For efficiency, visit
     163             :   // blocks in reverse order and walk backwards through each block. We
     164             :   // need several iterations to propagate liveness through nested loops.
     165      280036 :   BitVector live(maximum_environment_size_, zone());
     166      280036 :   BitVector worklist(block_count_, zone());
     167     4599900 :   for (int i = 0; i < block_count_; ++i) {
     168     4319864 :     worklist.Add(i);
     169             :   }
     170     1164534 :   while (!worklist.IsEmpty()) {
     171     7392608 :     for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
     172    14180754 :       if (!worklist.Contains(block_id)) {
     173             :         continue;
     174             :       }
     175             :       worklist.Remove(block_id);
     176     4583012 :       last_simulate_ = NULL;
     177             : 
     178    18093777 :       HBasicBlock* block = graph()->blocks()->at(block_id);
     179     4583012 :       UpdateLivenessAtBlockEnd(block, &live);
     180             : 
     181    35268807 :       for (HInstruction* instr = block->end(); instr != NULL;
     182             :            instr = instr->previous()) {
     183    30685795 :         UpdateLivenessAtInstruction(instr, &live);
     184             :       }
     185             : 
     186             :       // Reached the start of the block, do necessary bookkeeping:
     187             :       // store computed information for this block and add predecessors
     188             :       // to the work list as necessary.
     189     4583012 :       first_simulate_.Set(block_id, last_simulate_);
     190     4583012 :       first_simulate_invalid_for_index_[block_id]->CopyFrom(
     191     4583012 :           went_live_since_last_simulate_);
     192    13749036 :       if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
     193     1371136 :         for (int i = 0; i < block->predecessors()->length(); ++i) {
     194     1371136 :           worklist.Add(block->predecessors()->at(i)->block_id());
     195             :         }
     196     1176639 :         if (block->IsInlineReturnTarget()) {
     197       24858 :           worklist.Add(block->inlined_entry_block()->block_id());
     198             :         }
     199             :       }
     200             :     }
     201             :     // Only collect bind/lookup instructions during the first pass.
     202      302231 :     collect_markers_ = false;
     203             :   }
     204             : 
     205             :   // Analysis finished. Zap dead environment slots.
     206     2831312 :   for (int i = 0; i < markers_.length(); ++i) {
     207     6938257 :     ZapEnvironmentSlotsForInstruction(markers_[i]);
     208             :   }
     209     4599887 :   for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
     210     4319851 :     HBasicBlock* block = graph()->blocks()->at(block_id);
     211     4319851 :     UpdateLivenessAtBlockEnd(block, &live);
     212     4319849 :     ZapEnvironmentSlotsInSuccessors(block, &live);
     213             :   }
     214             : 
     215             :   // Finally, remove the HEnvironment{Bind,Lookup} markers.
     216     2831306 :   for (int i = 0; i < markers_.length(); ++i) {
     217     1275636 :     markers_[i]->DeleteAndReplaceWith(NULL);
     218             :   }
     219      280035 : }
     220             : 
     221             : 
     222             : #ifdef DEBUG
     223             : bool HEnvironmentLivenessAnalysisPhase::VerifyClosures(
     224             :     Handle<JSFunction> a, Handle<JSFunction> b) {
     225             :   Heap::RelocationLock for_heap_access(isolate()->heap());
     226             :   AllowHandleDereference for_verification;
     227             :   return a.is_identical_to(b);
     228             : }
     229             : #endif
     230             : 
     231             : }  // namespace internal
     232             : }  // namespace v8

Generated by: LCOV version 1.10