LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-escape-analysis.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 136 145 93.8 %
Date: 2017-04-26 Functions: 12 12 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             : #include "src/crankshaft/hydrogen-escape-analysis.h"
       6             : #include "src/objects-inl.h"
       7             : 
       8             : namespace v8 {
       9             : namespace internal {
      10             : 
      11             : 
      12       17609 : bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) {
      13       22486 :   for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
      14       36629 :     HValue* use = it.value();
      15       36629 :     if (use->HasEscapingOperandAt(it.index())) {
      16       13563 :       if (FLAG_trace_escape_analysis) {
      17             :         PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(),
      18           0 :                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
      19             :       }
      20       14143 :       return false;
      21             :     }
      22       23066 :     if (use->HasOutOfBoundsAccess(size)) {
      23           0 :       if (FLAG_trace_escape_analysis) {
      24             :         PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(),
      25           0 :                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
      26             :       }
      27             :       return false;
      28             :     }
      29       23066 :     int redefined_index = use->RedefinedOperandIndex();
      30       23066 :     if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) {
      31         580 :       if (FLAG_trace_escape_analysis) {
      32             :         PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(),
      33           0 :                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
      34             :       }
      35             :       return false;
      36             :     }
      37             :   }
      38        3466 :   return true;
      39             : }
      40             : 
      41             : 
      42      281359 : void HEscapeAnalysisPhase::CollectCapturedValues() {
      43     4383110 :   int block_count = graph()->blocks()->length();
      44     4383112 :   for (int i = 0; i < block_count; ++i) {
      45     4101751 :     HBasicBlock* block = graph()->blocks()->at(i);
      46    30579050 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      47             :       HInstruction* instr = it.Current();
      48    52954596 :       if (!instr->IsAllocate()) continue;
      49             :       HAllocate* allocate = HAllocate::cast(instr);
      50       21850 :       if (!allocate->size()->IsInteger32Constant()) continue;
      51       14216 :       int size_in_bytes = allocate->size()->GetInteger32Constant();
      52       14216 :       if (HasNoEscapingUses(instr, size_in_bytes)) {
      53         653 :         if (FLAG_trace_escape_analysis) {
      54             :           PrintF("#%d (%s) is being captured\n", instr->id(),
      55           0 :                  instr->Mnemonic());
      56             :         }
      57         653 :         captured_.Add(instr, zone());
      58             :       }
      59             :     }
      60             :   }
      61      281361 : }
      62             : 
      63             : 
      64       10961 : HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) {
      65       10961 :   Zone* zone = graph()->zone();
      66             :   HCapturedObject* state =
      67       10961 :       new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone);
      68       10961 :   state->InsertAfter(previous);
      69       10961 :   return state;
      70             : }
      71             : 
      72             : 
      73             : // Create a new state for replacing HAllocate instructions.
      74         653 : HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation(
      75             :     HInstruction* previous) {
      76         653 :   HConstant* undefined = graph()->GetConstantUndefined();
      77         653 :   HCapturedObject* state = NewState(previous);
      78        3563 :   for (int index = 0; index < number_of_values_; index++) {
      79        2910 :     state->SetOperandAt(index, undefined);
      80             :   }
      81         653 :   return state;
      82             : }
      83             : 
      84             : 
      85             : // Create a new state full of phis for loop header entries.
      86         942 : HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader(
      87             :     HInstruction* previous,
      88             :     HCapturedObject* old_state) {
      89         942 :   HBasicBlock* block = previous->block();
      90         942 :   HCapturedObject* state = NewState(previous);
      91        5521 :   for (int index = 0; index < number_of_values_; index++) {
      92             :     HValue* operand = old_state->OperandAt(index);
      93        4579 :     HPhi* phi = NewPhiAndInsert(block, operand, index);
      94        4579 :     state->SetOperandAt(index, phi);
      95             :   }
      96         942 :   return state;
      97             : }
      98             : 
      99             : 
     100             : // Create a new state by copying an existing one.
     101        9366 : HCapturedObject* HEscapeAnalysisPhase::NewStateCopy(
     102             :     HInstruction* previous,
     103             :     HCapturedObject* old_state) {
     104        9366 :   HCapturedObject* state = NewState(previous);
     105       55078 :   for (int index = 0; index < number_of_values_; index++) {
     106             :     HValue* operand = old_state->OperandAt(index);
     107       45712 :     state->SetOperandAt(index, operand);
     108             :   }
     109        9366 :   return state;
     110             : }
     111             : 
     112             : 
     113             : // Insert a newly created phi into the given block and fill all incoming
     114             : // edges with the given value.
     115       15952 : HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block,
     116             :                                             HValue* incoming_value,
     117             :                                             int index) {
     118       15952 :   Zone* zone = graph()->zone();
     119       15952 :   HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone);
     120      132105 :   for (int i = 0; i < block->predecessors()->length(); i++) {
     121      116153 :     phi->AddInput(incoming_value);
     122             :   }
     123       15952 :   block->AddPhi(phi);
     124       15952 :   return phi;
     125             : }
     126             : 
     127             : 
     128             : // Insert a newly created value check as a replacement for map checks.
     129        1390 : HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state,
     130        1390 :                                                    HCheckMaps* mapcheck) {
     131        1390 :   Zone* zone = graph()->zone();
     132             :   HValue* value = state->map_value();
     133             :   // TODO(mstarzinger): This will narrow a map check against a set of maps
     134             :   // down to the first element in the set. Revisit and fix this.
     135             :   HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value,
     136        2780 :                                         mapcheck->maps()->at(0), false);
     137        1390 :   check->InsertBefore(mapcheck);
     138        1390 :   return check;
     139             : }
     140             : 
     141             : 
     142             : // Replace a field load with a given value, forcing Smi representation if
     143             : // necessary.
     144         843 : HValue* HEscapeAnalysisPhase::NewLoadReplacement(
     145             :     HLoadNamedField* load, HValue* load_value) {
     146             :   HValue* replacement = load_value;
     147             :   Representation representation = load->representation();
     148         843 :   if (representation.IsSmiOrInteger32() || representation.IsDouble()) {
     149         385 :     Zone* zone = graph()->zone();
     150             :     HInstruction* new_instr = HForceRepresentation::New(
     151         385 :         graph()->isolate(), zone, NULL, load_value, representation);
     152         385 :     new_instr->InsertAfter(load);
     153             :     replacement = new_instr;
     154             :   }
     155         843 :   return replacement;
     156             : }
     157             : 
     158             : 
     159             : // Performs a forward data-flow analysis of all loads and stores on the
     160             : // given captured allocation. This uses a reverse post-order iteration
     161             : // over affected basic blocks. All non-escaping instructions are handled
     162             : // and replaced during the analysis.
     163         653 : void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) {
     164        1306 :   HBasicBlock* allocate_block = allocate->block();
     165       96212 :   block_states_.AddBlock(NULL, graph()->blocks()->length(), zone());
     166             : 
     167             :   // Iterate all blocks starting with the allocation block, since the
     168             :   // allocation cannot dominate blocks that come before.
     169             :   int start = allocate_block->block_id();
     170      191118 :   for (int i = start; i < graph()->blocks()->length(); i++) {
     171      426462 :     HBasicBlock* block = graph()->blocks()->at(i);
     172             :     HCapturedObject* state = StateAt(block);
     173             : 
     174             :     // Skip blocks that are not dominated by the captured allocation.
     175       94906 :     if (!allocate_block->Dominates(block) && allocate_block != block) continue;
     176       94866 :     if (FLAG_trace_escape_analysis) {
     177           0 :       PrintF("Analyzing data-flow in B%d\n", block->block_id());
     178             :     }
     179             : 
     180             :     // Go through all instructions of the current block.
     181      567275 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     182             :       HInstruction* instr = it.Current();
     183      472409 :       switch (instr->opcode()) {
     184             :         case HValue::kAllocate: {
     185        1138 :           if (instr != allocate) continue;
     186         653 :           state = NewStateForAllocation(allocate);
     187         653 :           break;
     188             :         }
     189             :         case HValue::kLoadNamedField: {
     190             :           HLoadNamedField* load = HLoadNamedField::cast(instr);
     191        3028 :           int index = load->access().offset() / kPointerSize;
     192        3028 :           if (load->object() != allocate) continue;
     193             :           DCHECK(load->access().IsInobject());
     194           0 :           HValue* replacement =
     195         843 :             NewLoadReplacement(load, state->OperandAt(index));
     196         843 :           load->DeleteAndReplaceWith(replacement);
     197         843 :           if (FLAG_trace_escape_analysis) {
     198             :             PrintF("Replacing load #%d with #%d (%s)\n", load->id(),
     199           0 :                    replacement->id(), replacement->Mnemonic());
     200             :           }
     201             :           break;
     202             :         }
     203             :         case HValue::kStoreNamedField: {
     204        4396 :           HStoreNamedField* store = HStoreNamedField::cast(instr);
     205        7670 :           int index = store->access().offset() / kPointerSize;
     206        7670 :           if (store->object() != allocate) continue;
     207             :           DCHECK(store->access().IsInobject());
     208        4396 :           state = NewStateCopy(store->previous(), state);
     209        4396 :           state->SetOperandAt(index, store->value());
     210        4396 :           if (store->has_transition()) {
     211         287 :             state->SetOperandAt(0, store->transition());
     212             :           }
     213        4396 :           if (store->HasObservableSideEffects()) {
     214             :             state->ReuseSideEffectsFromStore(store);
     215             :           }
     216        4396 :           store->DeleteAndReplaceWith(store->ActualValue());
     217        4396 :           if (FLAG_trace_escape_analysis) {
     218             :             PrintF("Replacing store #%d%s\n", instr->id(),
     219           0 :                    store->has_transition() ? " (with transition)" : "");
     220             :           }
     221             :           break;
     222             :         }
     223             :         case HValue::kArgumentsObject:
     224             :         case HValue::kCapturedObject:
     225             :         case HValue::kSimulate: {
     226      106411 :           for (int i = 0; i < instr->OperandCount(); i++) {
     227      106411 :             if (instr->OperandAt(i) != allocate) continue;
     228        1428 :             instr->SetOperandAt(i, state);
     229             :           }
     230             :           break;
     231             :         }
     232             :         case HValue::kCheckHeapObject: {
     233             :           HCheckHeapObject* check = HCheckHeapObject::cast(instr);
     234        1472 :           if (check->value() != allocate) continue;
     235         200 :           check->DeleteAndReplaceWith(check->ActualValue());
     236         200 :           break;
     237             :         }
     238             :         case HValue::kCheckMaps: {
     239             :           HCheckMaps* mapcheck = HCheckMaps::cast(instr);
     240        4839 :           if (mapcheck->value() != allocate) continue;
     241        1390 :           NewMapCheckAndInsert(state, mapcheck);
     242        1390 :           mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue());
     243        1390 :           break;
     244             :         }
     245             :         default:
     246             :           // Nothing to see here, move along ...
     247             :           break;
     248             :       }
     249             :     }
     250             : 
     251             :     // Propagate the block state forward to all successor blocks.
     252      426422 :     for (int i = 0; i < block->end()->SuccessorCount(); i++) {
     253      124257 :       HBasicBlock* succ = block->end()->SuccessorAt(i);
     254      118345 :       if (!allocate_block->Dominates(succ)) continue;
     255      118335 :       if (succ->predecessors()->length() == 1) {
     256             :         // Case 1: This is the only predecessor, just reuse state.
     257             :         SetStateAt(succ, state);
     258       35946 :       } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) {
     259             :         // Case 2: This is a state that enters a loop header, be
     260             :         // pessimistic about loop headers, add phis for all values.
     261         942 :         SetStateAt(succ, NewStateForLoopHeader(succ->first(), state));
     262       29092 :       } else if (StateAt(succ) == NULL) {
     263             :         // Case 3: This is the first state propagated forward to the
     264             :         // successor, leave a copy of the current state.
     265        4970 :         SetStateAt(succ, NewStateCopy(succ->first(), state));
     266             :       } else {
     267             :         // Case 4: This is a state that needs merging with previously
     268             :         // propagated states, potentially introducing new phis lazily or
     269             :         // adding values to existing phis.
     270             :         HCapturedObject* succ_state = StateAt(succ);
     271      120927 :         for (int index = 0; index < number_of_values_; index++) {
     272             :           HValue* operand = state->OperandAt(index);
     273      105780 :           HValue* succ_operand = succ_state->OperandAt(index);
     274      226707 :           if (succ_operand->IsPhi() && succ_operand->block() == succ) {
     275             :             // Phi already exists, add operand.
     276             :             HPhi* phi = HPhi::cast(succ_operand);
     277       52198 :             phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
     278       68729 :           } else if (succ_operand != operand) {
     279             :             // Phi does not exist, introduce one.
     280       11373 :             HPhi* phi = NewPhiAndInsert(succ, succ_operand, index);
     281       11373 :             phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
     282       11373 :             succ_state->SetOperandAt(index, phi);
     283             :           }
     284             :         }
     285             :       }
     286             :     }
     287             :   }
     288             : 
     289             :   // All uses have been handled.
     290             :   DCHECK(allocate->HasNoUses());
     291         653 :   allocate->DeleteAndReplaceWith(NULL);
     292         653 : }
     293             : 
     294             : 
     295         561 : void HEscapeAnalysisPhase::PerformScalarReplacement() {
     296        2428 :   for (int i = 0; i < captured_.length(); i++) {
     297        1867 :     HAllocate* allocate = HAllocate::cast(captured_.at(i));
     298             : 
     299             :     // Compute number of scalar values and start with clean slate.
     300         653 :     int size_in_bytes = allocate->size()->GetInteger32Constant();
     301         653 :     number_of_values_ = size_in_bytes / kPointerSize;
     302         653 :     number_of_objects_++;
     303             :     block_states_.Rewind(0);
     304             : 
     305             :     // Perform actual analysis step.
     306         653 :     AnalyzeDataFlow(allocate);
     307             : 
     308         653 :     cumulative_values_ += number_of_values_;
     309             :     DCHECK(allocate->HasNoUses());
     310             :     DCHECK(!allocate->IsLinked());
     311             :   }
     312         561 : }
     313             : 
     314             : 
     315      283729 : void HEscapeAnalysisPhase::Run() {
     316             :   // TODO(mstarzinger): We disable escape analysis with OSR for now, because
     317             :   // spill slots might be uninitialized. Needs investigation.
     318      567457 :   if (graph()->has_osr()) return;
     319      281361 :   int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations;
     320      281922 :   for (int i = 0; i < max_fixpoint_iteration_count; i++) {
     321      281361 :     CollectCapturedValues();
     322      281360 :     if (captured_.is_empty()) break;
     323         561 :     PerformScalarReplacement();
     324             :     captured_.Rewind(0);
     325             :   }
     326             : }
     327             : 
     328             : 
     329             : }  // namespace internal
     330             : }  // namespace v8

Generated by: LCOV version 1.10