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-flow-engine.h" 6#include "src/hydrogen-instructions.h" 7#include "src/hydrogen-removable-simulates.h" 8 9namespace v8 { 10namespace internal { 11 12class State : public ZoneObject { 13 public: 14 explicit State(Zone* zone) 15 : zone_(zone), mergelist_(2, zone), first_(true), mode_(NORMAL) { } 16 17 State* Process(HInstruction* instr, Zone* zone) { 18 if (FLAG_trace_removable_simulates) { 19 PrintF("[%s with state %p in B%d: #%d %s]\n", 20 mode_ == NORMAL ? "processing" : "collecting", 21 reinterpret_cast<void*>(this), instr->block()->block_id(), 22 instr->id(), instr->Mnemonic()); 23 } 24 // Forward-merge "trains" of simulates after an instruction with observable 25 // side effects to keep live ranges short. 26 if (mode_ == COLLECT_CONSECUTIVE_SIMULATES) { 27 if (instr->IsSimulate()) { 28 HSimulate* current_simulate = HSimulate::cast(instr); 29 if (current_simulate->is_candidate_for_removal() && 30 !current_simulate->ast_id().IsNone()) { 31 Remember(current_simulate); 32 return this; 33 } 34 } 35 FlushSimulates(); 36 mode_ = NORMAL; 37 } 38 // Ensure there's a non-foldable HSimulate before an HEnterInlined to avoid 39 // folding across HEnterInlined. 40 ASSERT(!(instr->IsEnterInlined() && 41 HSimulate::cast(instr->previous())->is_candidate_for_removal())); 42 if (instr->IsLeaveInlined() || instr->IsReturn()) { 43 // Never fold simulates from inlined environments into simulates in the 44 // outer environment. Simply remove all accumulated simulates without 45 // merging. This is safe because simulates after instructions with side 46 // effects are never added to the merge list. The same reasoning holds for 47 // return instructions. 48 RemoveSimulates(); 49 return this; 50 } 51 if (instr->IsControlInstruction()) { 52 // Merge the accumulated simulates at the end of the block. 53 FlushSimulates(); 54 return this; 55 } 56 // Skip the non-simulates and the first simulate. 57 if (!instr->IsSimulate()) return this; 58 if (first_) { 59 first_ = false; 60 return this; 61 } 62 HSimulate* current_simulate = HSimulate::cast(instr); 63 if (!current_simulate->is_candidate_for_removal()) { 64 Remember(current_simulate); 65 FlushSimulates(); 66 } else if (current_simulate->ast_id().IsNone()) { 67 ASSERT(current_simulate->next()->IsEnterInlined()); 68 FlushSimulates(); 69 } else if (current_simulate->previous()->HasObservableSideEffects()) { 70 Remember(current_simulate); 71 mode_ = COLLECT_CONSECUTIVE_SIMULATES; 72 } else { 73 Remember(current_simulate); 74 } 75 76 return this; 77 } 78 79 static State* Merge(State* succ_state, 80 HBasicBlock* succ_block, 81 State* pred_state, 82 HBasicBlock* pred_block, 83 Zone* zone) { 84 return (succ_state == NULL) 85 ? pred_state->Copy(succ_block, pred_block, zone) 86 : succ_state->Merge(succ_block, pred_state, pred_block, zone); 87 } 88 89 static State* Finish(State* state, HBasicBlock* block, Zone* zone) { 90 if (FLAG_trace_removable_simulates) { 91 PrintF("[preparing state %p for B%d]\n", reinterpret_cast<void*>(state), 92 block->block_id()); 93 } 94 // For our current local analysis, we should not remember simulates across 95 // block boundaries. 96 ASSERT(!state->HasRememberedSimulates()); 97 // Nasty heuristic: Never remove the first simulate in a block. This 98 // just so happens to have a beneficial effect on register allocation. 99 state->first_ = true; 100 return state; 101 } 102 103 private: 104 explicit State(const State& other) 105 : zone_(other.zone_), 106 mergelist_(other.mergelist_, other.zone_), 107 first_(other.first_), 108 mode_(other.mode_) { } 109 110 enum Mode { NORMAL, COLLECT_CONSECUTIVE_SIMULATES }; 111 112 bool HasRememberedSimulates() const { return !mergelist_.is_empty(); } 113 114 void Remember(HSimulate* sim) { 115 mergelist_.Add(sim, zone_); 116 } 117 118 void FlushSimulates() { 119 if (HasRememberedSimulates()) { 120 mergelist_.RemoveLast()->MergeWith(&mergelist_); 121 } 122 } 123 124 void RemoveSimulates() { 125 while (HasRememberedSimulates()) { 126 mergelist_.RemoveLast()->DeleteAndReplaceWith(NULL); 127 } 128 } 129 130 State* Copy(HBasicBlock* succ_block, HBasicBlock* pred_block, Zone* zone) { 131 State* copy = new(zone) State(*this); 132 if (FLAG_trace_removable_simulates) { 133 PrintF("[copy state %p from B%d to new state %p for B%d]\n", 134 reinterpret_cast<void*>(this), pred_block->block_id(), 135 reinterpret_cast<void*>(copy), succ_block->block_id()); 136 } 137 return copy; 138 } 139 140 State* Merge(HBasicBlock* succ_block, 141 State* pred_state, 142 HBasicBlock* pred_block, 143 Zone* zone) { 144 // For our current local analysis, we should not remember simulates across 145 // block boundaries. 146 ASSERT(!pred_state->HasRememberedSimulates()); 147 ASSERT(!HasRememberedSimulates()); 148 if (FLAG_trace_removable_simulates) { 149 PrintF("[merge state %p from B%d into %p for B%d]\n", 150 reinterpret_cast<void*>(pred_state), pred_block->block_id(), 151 reinterpret_cast<void*>(this), succ_block->block_id()); 152 } 153 return this; 154 } 155 156 Zone* zone_; 157 ZoneList<HSimulate*> mergelist_; 158 bool first_; 159 Mode mode_; 160}; 161 162 163// We don't use effects here. 164class Effects : public ZoneObject { 165 public: 166 explicit Effects(Zone* zone) { } 167 bool Disabled() { return true; } 168 void Process(HInstruction* instr, Zone* zone) { } 169 void Apply(State* state) { } 170 void Union(Effects* that, Zone* zone) { } 171}; 172 173 174void HMergeRemovableSimulatesPhase::Run() { 175 HFlowEngine<State, Effects> engine(graph(), zone()); 176 State* state = new(zone()) State(zone()); 177 engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), state); 178} 179 180} } // namespace v8::internal 181