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