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