11cb0ef41Sopenharmony_ci// Copyright 2019 the V8 project authors. All rights reserved. 21cb0ef41Sopenharmony_ci// Use of this source code is governed by a BSD-style license that can be 31cb0ef41Sopenharmony_ci// found in the LICENSE file. 41cb0ef41Sopenharmony_ci 51cb0ef41Sopenharmony_ci#include "src/compiler/csa-load-elimination.h" 61cb0ef41Sopenharmony_ci 71cb0ef41Sopenharmony_ci#include "src/compiler/common-operator.h" 81cb0ef41Sopenharmony_ci#include "src/compiler/node-matchers.h" 91cb0ef41Sopenharmony_ci#include "src/compiler/node-properties.h" 101cb0ef41Sopenharmony_ci#include "src/compiler/simplified-operator.h" 111cb0ef41Sopenharmony_ci 121cb0ef41Sopenharmony_cinamespace v8 { 131cb0ef41Sopenharmony_cinamespace internal { 141cb0ef41Sopenharmony_cinamespace compiler { 151cb0ef41Sopenharmony_ci 161cb0ef41Sopenharmony_ciReduction CsaLoadElimination::Reduce(Node* node) { 171cb0ef41Sopenharmony_ci if (FLAG_trace_turbo_load_elimination) { 181cb0ef41Sopenharmony_ci if (node->op()->EffectInputCount() > 0) { 191cb0ef41Sopenharmony_ci PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic()); 201cb0ef41Sopenharmony_ci if (node->op()->ValueInputCount() > 0) { 211cb0ef41Sopenharmony_ci PrintF("("); 221cb0ef41Sopenharmony_ci for (int i = 0; i < node->op()->ValueInputCount(); ++i) { 231cb0ef41Sopenharmony_ci if (i > 0) PrintF(", "); 241cb0ef41Sopenharmony_ci Node* const value = NodeProperties::GetValueInput(node, i); 251cb0ef41Sopenharmony_ci PrintF("#%d:%s", value->id(), value->op()->mnemonic()); 261cb0ef41Sopenharmony_ci } 271cb0ef41Sopenharmony_ci PrintF(")"); 281cb0ef41Sopenharmony_ci } 291cb0ef41Sopenharmony_ci PrintF("\n"); 301cb0ef41Sopenharmony_ci for (int i = 0; i < node->op()->EffectInputCount(); ++i) { 311cb0ef41Sopenharmony_ci Node* const effect = NodeProperties::GetEffectInput(node, i); 321cb0ef41Sopenharmony_ci if (AbstractState const* const state = node_states_.Get(effect)) { 331cb0ef41Sopenharmony_ci PrintF(" state[%i]: #%d:%s\n", i, effect->id(), 341cb0ef41Sopenharmony_ci effect->op()->mnemonic()); 351cb0ef41Sopenharmony_ci state->mutable_state.Print(); 361cb0ef41Sopenharmony_ci state->immutable_state.Print(); 371cb0ef41Sopenharmony_ci } else { 381cb0ef41Sopenharmony_ci PrintF(" no state[%i]: #%d:%s\n", i, effect->id(), 391cb0ef41Sopenharmony_ci effect->op()->mnemonic()); 401cb0ef41Sopenharmony_ci } 411cb0ef41Sopenharmony_ci } 421cb0ef41Sopenharmony_ci } 431cb0ef41Sopenharmony_ci } 441cb0ef41Sopenharmony_ci switch (node->opcode()) { 451cb0ef41Sopenharmony_ci case IrOpcode::kLoadFromObject: 461cb0ef41Sopenharmony_ci case IrOpcode::kLoadImmutableFromObject: 471cb0ef41Sopenharmony_ci return ReduceLoadFromObject(node, ObjectAccessOf(node->op())); 481cb0ef41Sopenharmony_ci case IrOpcode::kStoreToObject: 491cb0ef41Sopenharmony_ci case IrOpcode::kInitializeImmutableInObject: 501cb0ef41Sopenharmony_ci return ReduceStoreToObject(node, ObjectAccessOf(node->op())); 511cb0ef41Sopenharmony_ci case IrOpcode::kDebugBreak: 521cb0ef41Sopenharmony_ci case IrOpcode::kAbortCSADcheck: 531cb0ef41Sopenharmony_ci // Avoid changing optimizations in the presence of debug instructions. 541cb0ef41Sopenharmony_ci return PropagateInputState(node); 551cb0ef41Sopenharmony_ci case IrOpcode::kCall: 561cb0ef41Sopenharmony_ci return ReduceCall(node); 571cb0ef41Sopenharmony_ci case IrOpcode::kEffectPhi: 581cb0ef41Sopenharmony_ci return ReduceEffectPhi(node); 591cb0ef41Sopenharmony_ci case IrOpcode::kDead: 601cb0ef41Sopenharmony_ci return NoChange(); 611cb0ef41Sopenharmony_ci case IrOpcode::kStart: 621cb0ef41Sopenharmony_ci return ReduceStart(node); 631cb0ef41Sopenharmony_ci default: 641cb0ef41Sopenharmony_ci return ReduceOtherNode(node); 651cb0ef41Sopenharmony_ci } 661cb0ef41Sopenharmony_ci UNREACHABLE(); 671cb0ef41Sopenharmony_ci} 681cb0ef41Sopenharmony_ci 691cb0ef41Sopenharmony_cinamespace CsaLoadEliminationHelpers { 701cb0ef41Sopenharmony_ci 711cb0ef41Sopenharmony_cibool Subsumes(MachineRepresentation from, MachineRepresentation to) { 721cb0ef41Sopenharmony_ci if (from == to) return true; 731cb0ef41Sopenharmony_ci if (IsAnyTagged(from)) return IsAnyTagged(to); 741cb0ef41Sopenharmony_ci if (IsIntegral(from)) { 751cb0ef41Sopenharmony_ci return IsIntegral(to) && ElementSizeInBytes(from) >= ElementSizeInBytes(to); 761cb0ef41Sopenharmony_ci } 771cb0ef41Sopenharmony_ci return false; 781cb0ef41Sopenharmony_ci} 791cb0ef41Sopenharmony_ci 801cb0ef41Sopenharmony_cibool IsConstantObject(Node* object) { 811cb0ef41Sopenharmony_ci return object->opcode() == IrOpcode::kParameter || 821cb0ef41Sopenharmony_ci object->opcode() == IrOpcode::kLoadImmutable || 831cb0ef41Sopenharmony_ci NodeProperties::IsConstant(object); 841cb0ef41Sopenharmony_ci} 851cb0ef41Sopenharmony_ci 861cb0ef41Sopenharmony_cibool IsFreshObject(Node* object) { 871cb0ef41Sopenharmony_ci DCHECK_IMPLIES(NodeProperties::IsFreshObject(object), 881cb0ef41Sopenharmony_ci !IsConstantObject(object)); 891cb0ef41Sopenharmony_ci return NodeProperties::IsFreshObject(object); 901cb0ef41Sopenharmony_ci} 911cb0ef41Sopenharmony_ci 921cb0ef41Sopenharmony_ci} // namespace CsaLoadEliminationHelpers 931cb0ef41Sopenharmony_ci 941cb0ef41Sopenharmony_cinamespace Helpers = CsaLoadEliminationHelpers; 951cb0ef41Sopenharmony_ci 961cb0ef41Sopenharmony_ci// static 971cb0ef41Sopenharmony_citemplate <typename OuterKey> 981cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::IntersectWith( 991cb0ef41Sopenharmony_ci OuterMap<OuterKey>& to, const OuterMap<OuterKey>& from) { 1001cb0ef41Sopenharmony_ci FieldInfo empty_info; 1011cb0ef41Sopenharmony_ci for (const std::pair<OuterKey, InnerMap>& to_map : to) { 1021cb0ef41Sopenharmony_ci InnerMap to_map_copy(to_map.second); 1031cb0ef41Sopenharmony_ci OuterKey key = to_map.first; 1041cb0ef41Sopenharmony_ci InnerMap current_map = from.Get(key); 1051cb0ef41Sopenharmony_ci for (std::pair<Node*, FieldInfo> info : to_map.second) { 1061cb0ef41Sopenharmony_ci if (current_map.Get(info.first) != info.second) { 1071cb0ef41Sopenharmony_ci to_map_copy.Set(info.first, empty_info); 1081cb0ef41Sopenharmony_ci } 1091cb0ef41Sopenharmony_ci } 1101cb0ef41Sopenharmony_ci to.Set(key, to_map_copy); 1111cb0ef41Sopenharmony_ci } 1121cb0ef41Sopenharmony_ci} 1131cb0ef41Sopenharmony_ci 1141cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::IntersectWith(HalfState const* that) { 1151cb0ef41Sopenharmony_ci IntersectWith(fresh_entries_, that->fresh_entries_); 1161cb0ef41Sopenharmony_ci IntersectWith(constant_entries_, that->constant_entries_); 1171cb0ef41Sopenharmony_ci IntersectWith(arbitrary_entries_, that->arbitrary_entries_); 1181cb0ef41Sopenharmony_ci IntersectWith(fresh_unknown_entries_, that->fresh_unknown_entries_); 1191cb0ef41Sopenharmony_ci IntersectWith(constant_unknown_entries_, that->constant_unknown_entries_); 1201cb0ef41Sopenharmony_ci IntersectWith(arbitrary_unknown_entries_, that->arbitrary_unknown_entries_); 1211cb0ef41Sopenharmony_ci} 1221cb0ef41Sopenharmony_ci 1231cb0ef41Sopenharmony_ciCsaLoadElimination::HalfState const* CsaLoadElimination::HalfState::KillField( 1241cb0ef41Sopenharmony_ci Node* object, Node* offset, MachineRepresentation repr) const { 1251cb0ef41Sopenharmony_ci HalfState* result = zone_->New<HalfState>(*this); 1261cb0ef41Sopenharmony_ci UnknownOffsetInfos empty_unknown(zone_, InnerMap(zone_)); 1271cb0ef41Sopenharmony_ci IntPtrMatcher m(offset); 1281cb0ef41Sopenharmony_ci if (m.HasResolvedValue()) { 1291cb0ef41Sopenharmony_ci uint32_t num_offset = static_cast<uint32_t>(m.ResolvedValue()); 1301cb0ef41Sopenharmony_ci if (Helpers::IsFreshObject(object)) { 1311cb0ef41Sopenharmony_ci // May alias with: 1321cb0ef41Sopenharmony_ci // - The same object/offset 1331cb0ef41Sopenharmony_ci // - Arbitrary objects with the same offset 1341cb0ef41Sopenharmony_ci // - The same object, unkwown offset 1351cb0ef41Sopenharmony_ci // - Arbitrary objects with unkwown offset 1361cb0ef41Sopenharmony_ci result->KillOffsetInFresh(object, num_offset, repr); 1371cb0ef41Sopenharmony_ci KillOffset(result->arbitrary_entries_, num_offset, repr, zone_); 1381cb0ef41Sopenharmony_ci result->fresh_unknown_entries_.Set(object, InnerMap(zone_)); 1391cb0ef41Sopenharmony_ci result->arbitrary_unknown_entries_ = empty_unknown; 1401cb0ef41Sopenharmony_ci } else if (Helpers::IsConstantObject(object)) { 1411cb0ef41Sopenharmony_ci // May alias with: 1421cb0ef41Sopenharmony_ci // - Constant/arbitrary objects with the same offset 1431cb0ef41Sopenharmony_ci // - Constant/arbitrary objects with unkwown offset 1441cb0ef41Sopenharmony_ci KillOffset(result->constant_entries_, num_offset, repr, zone_); 1451cb0ef41Sopenharmony_ci KillOffset(result->arbitrary_entries_, num_offset, repr, zone_); 1461cb0ef41Sopenharmony_ci result->constant_unknown_entries_ = empty_unknown; 1471cb0ef41Sopenharmony_ci result->arbitrary_unknown_entries_ = empty_unknown; 1481cb0ef41Sopenharmony_ci } else { 1491cb0ef41Sopenharmony_ci // May alias with: 1501cb0ef41Sopenharmony_ci // - Any object with the same or unknown offset 1511cb0ef41Sopenharmony_ci KillOffset(result->fresh_entries_, num_offset, repr, zone_); 1521cb0ef41Sopenharmony_ci KillOffset(result->constant_entries_, num_offset, repr, zone_); 1531cb0ef41Sopenharmony_ci KillOffset(result->arbitrary_entries_, num_offset, repr, zone_); 1541cb0ef41Sopenharmony_ci result->fresh_unknown_entries_ = empty_unknown; 1551cb0ef41Sopenharmony_ci result->constant_unknown_entries_ = empty_unknown; 1561cb0ef41Sopenharmony_ci result->arbitrary_unknown_entries_ = empty_unknown; 1571cb0ef41Sopenharmony_ci } 1581cb0ef41Sopenharmony_ci } else { 1591cb0ef41Sopenharmony_ci ConstantOffsetInfos empty_constant(zone_, InnerMap(zone_)); 1601cb0ef41Sopenharmony_ci if (Helpers::IsFreshObject(object)) { 1611cb0ef41Sopenharmony_ci // May alias with: 1621cb0ef41Sopenharmony_ci // - The same object with any known/unknown offset 1631cb0ef41Sopenharmony_ci // - Arbitrary objects with any known/unknown offset 1641cb0ef41Sopenharmony_ci for (auto map : result->fresh_entries_) { 1651cb0ef41Sopenharmony_ci // TODO(manoskouk): Consider adding a map from fresh objects to offsets 1661cb0ef41Sopenharmony_ci // to implement this efficiently. 1671cb0ef41Sopenharmony_ci InnerMap map_copy(map.second); 1681cb0ef41Sopenharmony_ci map_copy.Set(object, FieldInfo()); 1691cb0ef41Sopenharmony_ci result->fresh_entries_.Set(map.first, map_copy); 1701cb0ef41Sopenharmony_ci } 1711cb0ef41Sopenharmony_ci result->fresh_unknown_entries_.Set(object, InnerMap(zone_)); 1721cb0ef41Sopenharmony_ci result->arbitrary_entries_ = empty_constant; 1731cb0ef41Sopenharmony_ci result->arbitrary_unknown_entries_ = empty_unknown; 1741cb0ef41Sopenharmony_ci } else if (Helpers::IsConstantObject(object)) { 1751cb0ef41Sopenharmony_ci // May alias with: 1761cb0ef41Sopenharmony_ci // - Constant/arbitrary objects with the any known/unknown offset 1771cb0ef41Sopenharmony_ci result->constant_entries_ = empty_constant; 1781cb0ef41Sopenharmony_ci result->constant_unknown_entries_ = empty_unknown; 1791cb0ef41Sopenharmony_ci result->arbitrary_entries_ = empty_constant; 1801cb0ef41Sopenharmony_ci result->arbitrary_unknown_entries_ = empty_unknown; 1811cb0ef41Sopenharmony_ci } else { 1821cb0ef41Sopenharmony_ci // May alias with anything. Clear the state. 1831cb0ef41Sopenharmony_ci return zone_->New<HalfState>(zone_); 1841cb0ef41Sopenharmony_ci } 1851cb0ef41Sopenharmony_ci } 1861cb0ef41Sopenharmony_ci 1871cb0ef41Sopenharmony_ci return result; 1881cb0ef41Sopenharmony_ci} 1891cb0ef41Sopenharmony_ci 1901cb0ef41Sopenharmony_ciCsaLoadElimination::HalfState const* CsaLoadElimination::HalfState::AddField( 1911cb0ef41Sopenharmony_ci Node* object, Node* offset, Node* value, MachineRepresentation repr) const { 1921cb0ef41Sopenharmony_ci HalfState* new_state = zone_->New<HalfState>(*this); 1931cb0ef41Sopenharmony_ci IntPtrMatcher m(offset); 1941cb0ef41Sopenharmony_ci if (m.HasResolvedValue()) { 1951cb0ef41Sopenharmony_ci uint32_t offset_num = static_cast<uint32_t>(m.ResolvedValue()); 1961cb0ef41Sopenharmony_ci ConstantOffsetInfos& infos = Helpers::IsFreshObject(object) 1971cb0ef41Sopenharmony_ci ? new_state->fresh_entries_ 1981cb0ef41Sopenharmony_ci : Helpers::IsConstantObject(object) 1991cb0ef41Sopenharmony_ci ? new_state->constant_entries_ 2001cb0ef41Sopenharmony_ci : new_state->arbitrary_entries_; 2011cb0ef41Sopenharmony_ci Update(infos, offset_num, object, FieldInfo(value, repr)); 2021cb0ef41Sopenharmony_ci } else { 2031cb0ef41Sopenharmony_ci UnknownOffsetInfos& infos = 2041cb0ef41Sopenharmony_ci Helpers::IsFreshObject(object) 2051cb0ef41Sopenharmony_ci ? new_state->fresh_unknown_entries_ 2061cb0ef41Sopenharmony_ci : Helpers::IsConstantObject(object) 2071cb0ef41Sopenharmony_ci ? new_state->constant_unknown_entries_ 2081cb0ef41Sopenharmony_ci : new_state->arbitrary_unknown_entries_; 2091cb0ef41Sopenharmony_ci Update(infos, object, offset, FieldInfo(value, repr)); 2101cb0ef41Sopenharmony_ci } 2111cb0ef41Sopenharmony_ci return new_state; 2121cb0ef41Sopenharmony_ci} 2131cb0ef41Sopenharmony_ci 2141cb0ef41Sopenharmony_ciCsaLoadElimination::FieldInfo CsaLoadElimination::HalfState::Lookup( 2151cb0ef41Sopenharmony_ci Node* object, Node* offset) const { 2161cb0ef41Sopenharmony_ci IntPtrMatcher m(offset); 2171cb0ef41Sopenharmony_ci if (m.HasResolvedValue()) { 2181cb0ef41Sopenharmony_ci uint32_t num_offset = static_cast<uint32_t>(m.ResolvedValue()); 2191cb0ef41Sopenharmony_ci const ConstantOffsetInfos& infos = Helpers::IsFreshObject(object) 2201cb0ef41Sopenharmony_ci ? fresh_entries_ 2211cb0ef41Sopenharmony_ci : Helpers::IsConstantObject(object) 2221cb0ef41Sopenharmony_ci ? constant_entries_ 2231cb0ef41Sopenharmony_ci : arbitrary_entries_; 2241cb0ef41Sopenharmony_ci return infos.Get(num_offset).Get(object); 2251cb0ef41Sopenharmony_ci } else { 2261cb0ef41Sopenharmony_ci const UnknownOffsetInfos& infos = Helpers::IsFreshObject(object) 2271cb0ef41Sopenharmony_ci ? fresh_unknown_entries_ 2281cb0ef41Sopenharmony_ci : Helpers::IsConstantObject(object) 2291cb0ef41Sopenharmony_ci ? constant_unknown_entries_ 2301cb0ef41Sopenharmony_ci : arbitrary_unknown_entries_; 2311cb0ef41Sopenharmony_ci return infos.Get(object).Get(offset); 2321cb0ef41Sopenharmony_ci } 2331cb0ef41Sopenharmony_ci} 2341cb0ef41Sopenharmony_ci 2351cb0ef41Sopenharmony_ci// static 2361cb0ef41Sopenharmony_ci// Kill all elements in {infos} that overlap with an element with {offset} and 2371cb0ef41Sopenharmony_ci// size {ElementSizeInBytes(repr)}. 2381cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::KillOffset(ConstantOffsetInfos& infos, 2391cb0ef41Sopenharmony_ci uint32_t offset, 2401cb0ef41Sopenharmony_ci MachineRepresentation repr, 2411cb0ef41Sopenharmony_ci Zone* zone) { 2421cb0ef41Sopenharmony_ci // All elements in the range [{offset}, {offset + ElementSizeInBytes(repr)}) 2431cb0ef41Sopenharmony_ci // are in the killed range. We do not need to traverse the inner maps, we can 2441cb0ef41Sopenharmony_ci // just clear them. 2451cb0ef41Sopenharmony_ci for (int i = 0; i < ElementSizeInBytes(repr); i++) { 2461cb0ef41Sopenharmony_ci infos.Set(offset + i, InnerMap(zone)); 2471cb0ef41Sopenharmony_ci } 2481cb0ef41Sopenharmony_ci 2491cb0ef41Sopenharmony_ci // Now we have to remove all elements in earlier offsets that overlap with an 2501cb0ef41Sopenharmony_ci // element in {offset}. 2511cb0ef41Sopenharmony_ci // The earliest offset that may overlap with {offset} is 2521cb0ef41Sopenharmony_ci // {kMaximumReprSizeInBytes - 1} before. 2531cb0ef41Sopenharmony_ci uint32_t initial_offset = offset >= kMaximumReprSizeInBytes - 1 2541cb0ef41Sopenharmony_ci ? offset - (kMaximumReprSizeInBytes - 1) 2551cb0ef41Sopenharmony_ci : 0; 2561cb0ef41Sopenharmony_ci // For all offsets from {initial_offset} to {offset}, we traverse the 2571cb0ef41Sopenharmony_ci // respective inner map, and reset all elements that are large enough to 2581cb0ef41Sopenharmony_ci // overlap with {offset}. 2591cb0ef41Sopenharmony_ci for (uint32_t i = initial_offset; i < offset; i++) { 2601cb0ef41Sopenharmony_ci InnerMap map_copy(infos.Get(i)); 2611cb0ef41Sopenharmony_ci for (const std::pair<Node*, FieldInfo> info : infos.Get(i)) { 2621cb0ef41Sopenharmony_ci if (info.second.representation != MachineRepresentation::kNone && 2631cb0ef41Sopenharmony_ci ElementSizeInBytes(info.second.representation) > 2641cb0ef41Sopenharmony_ci static_cast<int>(offset - i)) { 2651cb0ef41Sopenharmony_ci map_copy.Set(info.first, {}); 2661cb0ef41Sopenharmony_ci } 2671cb0ef41Sopenharmony_ci } 2681cb0ef41Sopenharmony_ci infos.Set(i, map_copy); 2691cb0ef41Sopenharmony_ci } 2701cb0ef41Sopenharmony_ci} 2711cb0ef41Sopenharmony_ci 2721cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::KillOffsetInFresh( 2731cb0ef41Sopenharmony_ci Node* const object, uint32_t offset, MachineRepresentation repr) { 2741cb0ef41Sopenharmony_ci for (int i = 0; i < ElementSizeInBytes(repr); i++) { 2751cb0ef41Sopenharmony_ci Update(fresh_entries_, offset + i, object, {}); 2761cb0ef41Sopenharmony_ci } 2771cb0ef41Sopenharmony_ci uint32_t initial_offset = offset >= kMaximumReprSizeInBytes - 1 2781cb0ef41Sopenharmony_ci ? offset - (kMaximumReprSizeInBytes - 1) 2791cb0ef41Sopenharmony_ci : 0; 2801cb0ef41Sopenharmony_ci for (uint32_t i = initial_offset; i < offset; i++) { 2811cb0ef41Sopenharmony_ci const FieldInfo& info = fresh_entries_.Get(i).Get(object); 2821cb0ef41Sopenharmony_ci if (info.representation != MachineRepresentation::kNone && 2831cb0ef41Sopenharmony_ci ElementSizeInBytes(info.representation) > 2841cb0ef41Sopenharmony_ci static_cast<int>(offset - i)) { 2851cb0ef41Sopenharmony_ci Update(fresh_entries_, i, object, {}); 2861cb0ef41Sopenharmony_ci } 2871cb0ef41Sopenharmony_ci } 2881cb0ef41Sopenharmony_ci} 2891cb0ef41Sopenharmony_ci 2901cb0ef41Sopenharmony_ci// static 2911cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::Print( 2921cb0ef41Sopenharmony_ci const CsaLoadElimination::HalfState::ConstantOffsetInfos& infos) { 2931cb0ef41Sopenharmony_ci for (const auto outer_entry : infos) { 2941cb0ef41Sopenharmony_ci for (const auto inner_entry : outer_entry.second) { 2951cb0ef41Sopenharmony_ci Node* object = inner_entry.first; 2961cb0ef41Sopenharmony_ci uint32_t offset = outer_entry.first; 2971cb0ef41Sopenharmony_ci FieldInfo info = inner_entry.second; 2981cb0ef41Sopenharmony_ci PrintF(" #%d:%s+(%d) -> #%d:%s [repr=%s]\n", object->id(), 2991cb0ef41Sopenharmony_ci object->op()->mnemonic(), offset, info.value->id(), 3001cb0ef41Sopenharmony_ci info.value->op()->mnemonic(), 3011cb0ef41Sopenharmony_ci MachineReprToString(info.representation)); 3021cb0ef41Sopenharmony_ci } 3031cb0ef41Sopenharmony_ci } 3041cb0ef41Sopenharmony_ci} 3051cb0ef41Sopenharmony_ci 3061cb0ef41Sopenharmony_ci// static 3071cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::Print( 3081cb0ef41Sopenharmony_ci const CsaLoadElimination::HalfState::UnknownOffsetInfos& infos) { 3091cb0ef41Sopenharmony_ci for (const auto outer_entry : infos) { 3101cb0ef41Sopenharmony_ci for (const auto inner_entry : outer_entry.second) { 3111cb0ef41Sopenharmony_ci Node* object = outer_entry.first; 3121cb0ef41Sopenharmony_ci Node* offset = inner_entry.first; 3131cb0ef41Sopenharmony_ci FieldInfo info = inner_entry.second; 3141cb0ef41Sopenharmony_ci PrintF(" #%d:%s+#%d:%s -> #%d:%s [repr=%s]\n", object->id(), 3151cb0ef41Sopenharmony_ci object->op()->mnemonic(), offset->id(), offset->op()->mnemonic(), 3161cb0ef41Sopenharmony_ci info.value->id(), info.value->op()->mnemonic(), 3171cb0ef41Sopenharmony_ci MachineReprToString(info.representation)); 3181cb0ef41Sopenharmony_ci } 3191cb0ef41Sopenharmony_ci } 3201cb0ef41Sopenharmony_ci} 3211cb0ef41Sopenharmony_ci 3221cb0ef41Sopenharmony_civoid CsaLoadElimination::HalfState::Print() const { 3231cb0ef41Sopenharmony_ci Print(fresh_entries_); 3241cb0ef41Sopenharmony_ci Print(constant_entries_); 3251cb0ef41Sopenharmony_ci Print(arbitrary_entries_); 3261cb0ef41Sopenharmony_ci Print(fresh_unknown_entries_); 3271cb0ef41Sopenharmony_ci Print(constant_unknown_entries_); 3281cb0ef41Sopenharmony_ci Print(arbitrary_unknown_entries_); 3291cb0ef41Sopenharmony_ci} 3301cb0ef41Sopenharmony_ci 3311cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceLoadFromObject(Node* node, 3321cb0ef41Sopenharmony_ci ObjectAccess const& access) { 3331cb0ef41Sopenharmony_ci DCHECK(node->opcode() == IrOpcode::kLoadFromObject || 3341cb0ef41Sopenharmony_ci node->opcode() == IrOpcode::kLoadImmutableFromObject); 3351cb0ef41Sopenharmony_ci Node* object = NodeProperties::GetValueInput(node, 0); 3361cb0ef41Sopenharmony_ci Node* offset = NodeProperties::GetValueInput(node, 1); 3371cb0ef41Sopenharmony_ci Node* effect = NodeProperties::GetEffectInput(node); 3381cb0ef41Sopenharmony_ci AbstractState const* state = node_states_.Get(effect); 3391cb0ef41Sopenharmony_ci if (state == nullptr) return NoChange(); 3401cb0ef41Sopenharmony_ci bool is_mutable = node->opcode() == IrOpcode::kLoadFromObject; 3411cb0ef41Sopenharmony_ci // We should never find a field in the wrong half-state. 3421cb0ef41Sopenharmony_ci DCHECK((is_mutable ? &state->immutable_state : &state->mutable_state) 3431cb0ef41Sopenharmony_ci ->Lookup(object, offset) 3441cb0ef41Sopenharmony_ci .IsEmpty()); 3451cb0ef41Sopenharmony_ci HalfState const* half_state = 3461cb0ef41Sopenharmony_ci is_mutable ? &state->mutable_state : &state->immutable_state; 3471cb0ef41Sopenharmony_ci 3481cb0ef41Sopenharmony_ci MachineRepresentation representation = access.machine_type.representation(); 3491cb0ef41Sopenharmony_ci FieldInfo lookup_result = half_state->Lookup(object, offset); 3501cb0ef41Sopenharmony_ci if (!lookup_result.IsEmpty()) { 3511cb0ef41Sopenharmony_ci // Make sure we don't reuse values that were recorded with a different 3521cb0ef41Sopenharmony_ci // representation or resurrect dead {replacement} nodes. 3531cb0ef41Sopenharmony_ci MachineRepresentation from = lookup_result.representation; 3541cb0ef41Sopenharmony_ci if (Helpers::Subsumes(from, representation) && 3551cb0ef41Sopenharmony_ci !lookup_result.value->IsDead()) { 3561cb0ef41Sopenharmony_ci Node* replacement = 3571cb0ef41Sopenharmony_ci TruncateAndExtend(lookup_result.value, from, access.machine_type); 3581cb0ef41Sopenharmony_ci ReplaceWithValue(node, replacement, effect); 3591cb0ef41Sopenharmony_ci // This might have opened an opportunity for escape analysis to eliminate 3601cb0ef41Sopenharmony_ci // the object altogether. 3611cb0ef41Sopenharmony_ci Revisit(object); 3621cb0ef41Sopenharmony_ci return Replace(replacement); 3631cb0ef41Sopenharmony_ci } 3641cb0ef41Sopenharmony_ci } 3651cb0ef41Sopenharmony_ci half_state = half_state->AddField(object, offset, node, representation); 3661cb0ef41Sopenharmony_ci 3671cb0ef41Sopenharmony_ci AbstractState const* new_state = 3681cb0ef41Sopenharmony_ci is_mutable 3691cb0ef41Sopenharmony_ci ? zone()->New<AbstractState>(*half_state, state->immutable_state) 3701cb0ef41Sopenharmony_ci : zone()->New<AbstractState>(state->mutable_state, *half_state); 3711cb0ef41Sopenharmony_ci 3721cb0ef41Sopenharmony_ci return UpdateState(node, new_state); 3731cb0ef41Sopenharmony_ci} 3741cb0ef41Sopenharmony_ci 3751cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceStoreToObject(Node* node, 3761cb0ef41Sopenharmony_ci ObjectAccess const& access) { 3771cb0ef41Sopenharmony_ci DCHECK(node->opcode() == IrOpcode::kStoreToObject || 3781cb0ef41Sopenharmony_ci node->opcode() == IrOpcode::kInitializeImmutableInObject); 3791cb0ef41Sopenharmony_ci Node* object = NodeProperties::GetValueInput(node, 0); 3801cb0ef41Sopenharmony_ci Node* offset = NodeProperties::GetValueInput(node, 1); 3811cb0ef41Sopenharmony_ci Node* value = NodeProperties::GetValueInput(node, 2); 3821cb0ef41Sopenharmony_ci Node* effect = NodeProperties::GetEffectInput(node); 3831cb0ef41Sopenharmony_ci AbstractState const* state = node_states_.Get(effect); 3841cb0ef41Sopenharmony_ci if (state == nullptr) return NoChange(); 3851cb0ef41Sopenharmony_ci MachineRepresentation repr = access.machine_type.representation(); 3861cb0ef41Sopenharmony_ci if (node->opcode() == IrOpcode::kStoreToObject) { 3871cb0ef41Sopenharmony_ci // We should not find the field in the wrong half-state. 3881cb0ef41Sopenharmony_ci DCHECK(state->immutable_state.Lookup(object, offset).IsEmpty()); 3891cb0ef41Sopenharmony_ci HalfState const* mutable_state = 3901cb0ef41Sopenharmony_ci state->mutable_state.KillField(object, offset, repr); 3911cb0ef41Sopenharmony_ci mutable_state = mutable_state->AddField(object, offset, value, repr); 3921cb0ef41Sopenharmony_ci AbstractState const* new_state = 3931cb0ef41Sopenharmony_ci zone()->New<AbstractState>(*mutable_state, state->immutable_state); 3941cb0ef41Sopenharmony_ci return UpdateState(node, new_state); 3951cb0ef41Sopenharmony_ci } else { 3961cb0ef41Sopenharmony_ci // We should not find the field in the wrong half-state. 3971cb0ef41Sopenharmony_ci DCHECK(state->mutable_state.Lookup(object, offset).IsEmpty()); 3981cb0ef41Sopenharmony_ci // We should not initialize the same immutable field twice. 3991cb0ef41Sopenharmony_ci DCHECK(state->immutable_state.Lookup(object, offset).IsEmpty()); 4001cb0ef41Sopenharmony_ci HalfState const* immutable_state = 4011cb0ef41Sopenharmony_ci state->immutable_state.AddField(object, offset, value, repr); 4021cb0ef41Sopenharmony_ci AbstractState const* new_state = 4031cb0ef41Sopenharmony_ci zone()->New<AbstractState>(state->mutable_state, *immutable_state); 4041cb0ef41Sopenharmony_ci return UpdateState(node, new_state); 4051cb0ef41Sopenharmony_ci } 4061cb0ef41Sopenharmony_ci} 4071cb0ef41Sopenharmony_ci 4081cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceEffectPhi(Node* node) { 4091cb0ef41Sopenharmony_ci Node* const effect0 = NodeProperties::GetEffectInput(node, 0); 4101cb0ef41Sopenharmony_ci Node* const control = NodeProperties::GetControlInput(node); 4111cb0ef41Sopenharmony_ci AbstractState const* state0 = node_states_.Get(effect0); 4121cb0ef41Sopenharmony_ci if (state0 == nullptr) return NoChange(); 4131cb0ef41Sopenharmony_ci if (control->opcode() == IrOpcode::kLoop) { 4141cb0ef41Sopenharmony_ci // Here we rely on having only reducible loops: 4151cb0ef41Sopenharmony_ci // The loop entry edge always dominates the header, so we can just take 4161cb0ef41Sopenharmony_ci // the state from the first input, and compute the loop state based on it. 4171cb0ef41Sopenharmony_ci AbstractState const* state = ComputeLoopState(node, state0); 4181cb0ef41Sopenharmony_ci return UpdateState(node, state); 4191cb0ef41Sopenharmony_ci } 4201cb0ef41Sopenharmony_ci DCHECK_EQ(IrOpcode::kMerge, control->opcode()); 4211cb0ef41Sopenharmony_ci 4221cb0ef41Sopenharmony_ci // Shortcut for the case when we do not know anything about some input. 4231cb0ef41Sopenharmony_ci int const input_count = node->op()->EffectInputCount(); 4241cb0ef41Sopenharmony_ci for (int i = 1; i < input_count; ++i) { 4251cb0ef41Sopenharmony_ci Node* const effect = NodeProperties::GetEffectInput(node, i); 4261cb0ef41Sopenharmony_ci if (node_states_.Get(effect) == nullptr) return NoChange(); 4271cb0ef41Sopenharmony_ci } 4281cb0ef41Sopenharmony_ci 4291cb0ef41Sopenharmony_ci // Make a copy of the first input's state and intersect it with the state 4301cb0ef41Sopenharmony_ci // from other inputs. 4311cb0ef41Sopenharmony_ci // TODO(manoskouk): Consider computing phis for at least a subset of the 4321cb0ef41Sopenharmony_ci // state. 4331cb0ef41Sopenharmony_ci AbstractState* state = zone()->New<AbstractState>(*state0); 4341cb0ef41Sopenharmony_ci for (int i = 1; i < input_count; ++i) { 4351cb0ef41Sopenharmony_ci Node* const input = NodeProperties::GetEffectInput(node, i); 4361cb0ef41Sopenharmony_ci state->IntersectWith(node_states_.Get(input)); 4371cb0ef41Sopenharmony_ci } 4381cb0ef41Sopenharmony_ci return UpdateState(node, state); 4391cb0ef41Sopenharmony_ci} 4401cb0ef41Sopenharmony_ci 4411cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceStart(Node* node) { 4421cb0ef41Sopenharmony_ci return UpdateState(node, empty_state()); 4431cb0ef41Sopenharmony_ci} 4441cb0ef41Sopenharmony_ci 4451cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceCall(Node* node) { 4461cb0ef41Sopenharmony_ci Node* value = NodeProperties::GetValueInput(node, 0); 4471cb0ef41Sopenharmony_ci ExternalReferenceMatcher m(value); 4481cb0ef41Sopenharmony_ci if (m.Is(ExternalReference::check_object_type())) { 4491cb0ef41Sopenharmony_ci return PropagateInputState(node); 4501cb0ef41Sopenharmony_ci } 4511cb0ef41Sopenharmony_ci return ReduceOtherNode(node); 4521cb0ef41Sopenharmony_ci} 4531cb0ef41Sopenharmony_ci 4541cb0ef41Sopenharmony_ciReduction CsaLoadElimination::ReduceOtherNode(Node* node) { 4551cb0ef41Sopenharmony_ci if (node->op()->EffectInputCount() == 1 && 4561cb0ef41Sopenharmony_ci node->op()->EffectOutputCount() == 1) { 4571cb0ef41Sopenharmony_ci Node* const effect = NodeProperties::GetEffectInput(node); 4581cb0ef41Sopenharmony_ci AbstractState const* state = node_states_.Get(effect); 4591cb0ef41Sopenharmony_ci // If we do not know anything about the predecessor, do not propagate just 4601cb0ef41Sopenharmony_ci // yet because we will have to recompute anyway once we compute the 4611cb0ef41Sopenharmony_ci // predecessor. 4621cb0ef41Sopenharmony_ci if (state == nullptr) return NoChange(); 4631cb0ef41Sopenharmony_ci // If this {node} has some uncontrolled side effects, set its state to 4641cb0ef41Sopenharmony_ci // the immutable half-state of its input state, otherwise to its input 4651cb0ef41Sopenharmony_ci // state. 4661cb0ef41Sopenharmony_ci return UpdateState( 4671cb0ef41Sopenharmony_ci node, node->op()->HasProperty(Operator::kNoWrite) 4681cb0ef41Sopenharmony_ci ? state 4691cb0ef41Sopenharmony_ci : zone()->New<AbstractState>(HalfState(zone()), 4701cb0ef41Sopenharmony_ci state->immutable_state)); 4711cb0ef41Sopenharmony_ci } 4721cb0ef41Sopenharmony_ci DCHECK_EQ(0, node->op()->EffectOutputCount()); 4731cb0ef41Sopenharmony_ci return NoChange(); 4741cb0ef41Sopenharmony_ci} 4751cb0ef41Sopenharmony_ci 4761cb0ef41Sopenharmony_ciReduction CsaLoadElimination::UpdateState(Node* node, 4771cb0ef41Sopenharmony_ci AbstractState const* state) { 4781cb0ef41Sopenharmony_ci AbstractState const* original = node_states_.Get(node); 4791cb0ef41Sopenharmony_ci // Only signal that the {node} has Changed, if the information about {state} 4801cb0ef41Sopenharmony_ci // has changed wrt. the {original}. 4811cb0ef41Sopenharmony_ci if (state != original) { 4821cb0ef41Sopenharmony_ci if (original == nullptr || !state->Equals(original)) { 4831cb0ef41Sopenharmony_ci node_states_.Set(node, state); 4841cb0ef41Sopenharmony_ci return Changed(node); 4851cb0ef41Sopenharmony_ci } 4861cb0ef41Sopenharmony_ci } 4871cb0ef41Sopenharmony_ci return NoChange(); 4881cb0ef41Sopenharmony_ci} 4891cb0ef41Sopenharmony_ci 4901cb0ef41Sopenharmony_ciReduction CsaLoadElimination::PropagateInputState(Node* node) { 4911cb0ef41Sopenharmony_ci Node* const effect = NodeProperties::GetEffectInput(node); 4921cb0ef41Sopenharmony_ci AbstractState const* state = node_states_.Get(effect); 4931cb0ef41Sopenharmony_ci if (state == nullptr) return NoChange(); 4941cb0ef41Sopenharmony_ci return UpdateState(node, state); 4951cb0ef41Sopenharmony_ci} 4961cb0ef41Sopenharmony_ci 4971cb0ef41Sopenharmony_ciCsaLoadElimination::AbstractState const* CsaLoadElimination::ComputeLoopState( 4981cb0ef41Sopenharmony_ci Node* node, AbstractState const* state) const { 4991cb0ef41Sopenharmony_ci DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi); 5001cb0ef41Sopenharmony_ci std::queue<Node*> queue; 5011cb0ef41Sopenharmony_ci std::unordered_set<Node*> visited; 5021cb0ef41Sopenharmony_ci visited.insert(node); 5031cb0ef41Sopenharmony_ci for (int i = 1; i < node->InputCount() - 1; ++i) { 5041cb0ef41Sopenharmony_ci queue.push(node->InputAt(i)); 5051cb0ef41Sopenharmony_ci } 5061cb0ef41Sopenharmony_ci while (!queue.empty()) { 5071cb0ef41Sopenharmony_ci Node* const current = queue.front(); 5081cb0ef41Sopenharmony_ci queue.pop(); 5091cb0ef41Sopenharmony_ci if (visited.insert(current).second) { 5101cb0ef41Sopenharmony_ci if (current->opcode() == IrOpcode::kStoreToObject) { 5111cb0ef41Sopenharmony_ci Node* object = NodeProperties::GetValueInput(current, 0); 5121cb0ef41Sopenharmony_ci Node* offset = NodeProperties::GetValueInput(current, 1); 5131cb0ef41Sopenharmony_ci MachineRepresentation repr = 5141cb0ef41Sopenharmony_ci ObjectAccessOf(current->op()).machine_type.representation(); 5151cb0ef41Sopenharmony_ci const HalfState* new_mutable_state = 5161cb0ef41Sopenharmony_ci state->mutable_state.KillField(object, offset, repr); 5171cb0ef41Sopenharmony_ci state = zone()->New<AbstractState>(*new_mutable_state, 5181cb0ef41Sopenharmony_ci state->immutable_state); 5191cb0ef41Sopenharmony_ci } else if (current->opcode() == IrOpcode::kInitializeImmutableInObject) { 5201cb0ef41Sopenharmony_ci#if DEBUG 5211cb0ef41Sopenharmony_ci // We are not allowed to reset an immutable (object, offset) pair. 5221cb0ef41Sopenharmony_ci Node* object = NodeProperties::GetValueInput(current, 0); 5231cb0ef41Sopenharmony_ci Node* offset = NodeProperties::GetValueInput(current, 1); 5241cb0ef41Sopenharmony_ci CHECK(state->immutable_state.Lookup(object, offset).IsEmpty()); 5251cb0ef41Sopenharmony_ci#endif 5261cb0ef41Sopenharmony_ci } else if (!current->op()->HasProperty(Operator::kNoWrite)) { 5271cb0ef41Sopenharmony_ci return zone()->New<AbstractState>(HalfState(zone()), 5281cb0ef41Sopenharmony_ci state->immutable_state); 5291cb0ef41Sopenharmony_ci } 5301cb0ef41Sopenharmony_ci for (int i = 0; i < current->op()->EffectInputCount(); ++i) { 5311cb0ef41Sopenharmony_ci queue.push(NodeProperties::GetEffectInput(current, i)); 5321cb0ef41Sopenharmony_ci } 5331cb0ef41Sopenharmony_ci } 5341cb0ef41Sopenharmony_ci } 5351cb0ef41Sopenharmony_ci return state; 5361cb0ef41Sopenharmony_ci} 5371cb0ef41Sopenharmony_ci 5381cb0ef41Sopenharmony_ciNode* CsaLoadElimination::TruncateAndExtend(Node* node, 5391cb0ef41Sopenharmony_ci MachineRepresentation from, 5401cb0ef41Sopenharmony_ci MachineType to) { 5411cb0ef41Sopenharmony_ci DCHECK(Helpers::Subsumes(from, to.representation())); 5421cb0ef41Sopenharmony_ci DCHECK_GE(ElementSizeInBytes(from), ElementSizeInBytes(to.representation())); 5431cb0ef41Sopenharmony_ci 5441cb0ef41Sopenharmony_ci if (to == MachineType::Int8() || to == MachineType::Int16()) { 5451cb0ef41Sopenharmony_ci // 1st case: We want to eliminate a signed 8/16-bit load using the value 5461cb0ef41Sopenharmony_ci // from a previous subsuming load or store. Since that value might be 5471cb0ef41Sopenharmony_ci // outside 8/16-bit range, we first truncate it accordingly. Then we 5481cb0ef41Sopenharmony_ci // sign-extend the result to 32-bit. 5491cb0ef41Sopenharmony_ci DCHECK_EQ(to.semantic(), MachineSemantic::kInt32); 5501cb0ef41Sopenharmony_ci if (from == MachineRepresentation::kWord64) { 5511cb0ef41Sopenharmony_ci node = graph()->NewNode(machine()->TruncateInt64ToInt32(), node); 5521cb0ef41Sopenharmony_ci } 5531cb0ef41Sopenharmony_ci int shift = 32 - 8 * ElementSizeInBytes(to.representation()); 5541cb0ef41Sopenharmony_ci return graph()->NewNode(machine()->Word32Sar(), 5551cb0ef41Sopenharmony_ci graph()->NewNode(machine()->Word32Shl(), node, 5561cb0ef41Sopenharmony_ci jsgraph()->Int32Constant(shift)), 5571cb0ef41Sopenharmony_ci jsgraph()->Int32Constant(shift)); 5581cb0ef41Sopenharmony_ci } else if (to == MachineType::Uint8() || to == MachineType::Uint16()) { 5591cb0ef41Sopenharmony_ci // 2nd case: We want to eliminate an unsigned 8/16-bit load using the value 5601cb0ef41Sopenharmony_ci // from a previous subsuming load or store. Since that value might be 5611cb0ef41Sopenharmony_ci // outside 8/16-bit range, we first truncate it accordingly. 5621cb0ef41Sopenharmony_ci if (from == MachineRepresentation::kWord64) { 5631cb0ef41Sopenharmony_ci node = graph()->NewNode(machine()->TruncateInt64ToInt32(), node); 5641cb0ef41Sopenharmony_ci } 5651cb0ef41Sopenharmony_ci int mask = (1 << 8 * ElementSizeInBytes(to.representation())) - 1; 5661cb0ef41Sopenharmony_ci return graph()->NewNode(machine()->Word32And(), node, 5671cb0ef41Sopenharmony_ci jsgraph()->Int32Constant(mask)); 5681cb0ef41Sopenharmony_ci } else if (from == MachineRepresentation::kWord64 && 5691cb0ef41Sopenharmony_ci to.representation() == MachineRepresentation::kWord32) { 5701cb0ef41Sopenharmony_ci // 3rd case: Truncate 64-bits into 32-bits. 5711cb0ef41Sopenharmony_ci return graph()->NewNode(machine()->TruncateInt64ToInt32(), node); 5721cb0ef41Sopenharmony_ci } else { 5731cb0ef41Sopenharmony_ci // 4th case: No need for truncation. 5741cb0ef41Sopenharmony_ci DCHECK((from == to.representation() && 5751cb0ef41Sopenharmony_ci (from == MachineRepresentation::kWord32 || 5761cb0ef41Sopenharmony_ci from == MachineRepresentation::kWord64 || !IsIntegral(from))) || 5771cb0ef41Sopenharmony_ci (IsAnyTagged(from) && IsAnyTagged(to.representation()))); 5781cb0ef41Sopenharmony_ci return node; 5791cb0ef41Sopenharmony_ci } 5801cb0ef41Sopenharmony_ci} 5811cb0ef41Sopenharmony_ci 5821cb0ef41Sopenharmony_ciCommonOperatorBuilder* CsaLoadElimination::common() const { 5831cb0ef41Sopenharmony_ci return jsgraph()->common(); 5841cb0ef41Sopenharmony_ci} 5851cb0ef41Sopenharmony_ci 5861cb0ef41Sopenharmony_ciMachineOperatorBuilder* CsaLoadElimination::machine() const { 5871cb0ef41Sopenharmony_ci return jsgraph()->machine(); 5881cb0ef41Sopenharmony_ci} 5891cb0ef41Sopenharmony_ci 5901cb0ef41Sopenharmony_ciGraph* CsaLoadElimination::graph() const { return jsgraph()->graph(); } 5911cb0ef41Sopenharmony_ci 5921cb0ef41Sopenharmony_ciIsolate* CsaLoadElimination::isolate() const { return jsgraph()->isolate(); } 5931cb0ef41Sopenharmony_ci 5941cb0ef41Sopenharmony_ci} // namespace compiler 5951cb0ef41Sopenharmony_ci} // namespace internal 5961cb0ef41Sopenharmony_ci} // namespace v8 597