1/*
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "ecmascript/compiler/escape_analysis.h"
17
18namespace panda::ecmascript::kungfu {
19
20VirtualObject::VirtualObject(size_t numIn, Chunk* chunk)
21    : fields_(chunk), users_(chunk)
22{
23    for (size_t i = 0; i < numIn; i++) {
24        FieldLocation tmp;
25        fields_.emplace_back(tmp);
26    }
27}
28
29void VirtualObject::SetEscaped()
30{
31    escaped_ = true;
32}
33
34bool VirtualObject::IsEscaped() const
35{
36    return escaped_;
37}
38
39FieldLocation VirtualObject::GetField(size_t offset)
40{
41    constexpr size_t fieldSize = 8;
42    ASSERT(offset % fieldSize == 0);
43    if (offset / fieldSize >= fields_.size()) {
44        return FieldLocation::Invalid();
45    }
46    return fields_.at(offset/fieldSize);
47}
48
49size_t FieldLocation::maxid = 0;
50
51ChunkVector<GateRef>& VirtualObject::GetUsers()
52{
53    return users_;
54}
55
56void VirtualObject::ClearUsers()
57{
58    users_.clear();
59}
60
61void VirtualObject::AddUser(GateRef gate)
62{
63    users_.push_back(gate);
64}
65
66GateInfo::GateInfo(Circuit* circuit, GateRef curGate, EscapeAnalysis* escapeAnalysis, Chunk* chunk)
67    : circuit_(circuit), acc_(circuit), curGate_(curGate), escapeAnalysis_(escapeAnalysis), state_(chunk)
68{
69    if (acc_.GetOpCode(curGate) == OpCode::DEPEND_SELECTOR) {
70        state_ = MergeState(curGate);
71    } else {
72        ASSERT(acc_.GetDependCount(curGate) <= 1);
73        if (acc_.GetDependCount(curGate) == 1) {
74            state_ = escapeAnalysis_->GetOrCreateState(acc_.GetDep(curGate));
75        }
76    }
77}
78
79GateInfo::~GateInfo()
80{
81    State& preState = escapeAnalysis_->GetOrCreateState(curGate_);
82    if (state_.IsMapEqual(preState) ||
83        object_ != escapeAnalysis_->TryGetVirtualObject(curGate_)) {
84        escapeAnalysis_->SetReplaceGate(curGate_);
85    }
86    escapeAnalysis_->SetState(curGate_, state_);
87
88    escapeAnalysis_->SetVirtualObject(curGate_, object_);
89    escapeAnalysis_->SetReplacement(curGate_, replacement_);
90}
91
92GateRef GateInfo::GetCurrentGate() const
93{
94    return curGate_;
95}
96
97State GateInfo::MergeState(GateRef gate)
98{
99    size_t numIn = acc_.GetDependCount(gate);
100    State& preState = escapeAnalysis_->GetOrCreateState(acc_.GetDep(gate, 0));
101    State result = preState;
102    for (auto fieldValue : preState) {
103        FieldLocation field = fieldValue.first;
104        GateRef value = fieldValue.second;
105        ASSERT(field != FieldLocation::Invalid());
106        if (value != Circuit::NullGate()) {
107            std::vector<GateRef> input;
108            input.push_back(acc_.GetState(gate));
109            input.push_back(value);
110            size_t numAliveState = 1;
111            bool differentFlag = false;
112            for (size_t i = 1; i < numIn; i++) {
113                State& inputState = escapeAnalysis_->GetOrCreateState(acc_.GetDep(gate, i));
114                GateRef inputValue = inputState.GetFieldValue(field);
115                if (inputValue != Circuit::NullGate()) {
116                    numAliveState++;
117                }
118                if (inputValue != value) {
119                    differentFlag = true;
120                }
121                input.push_back(inputValue);
122            }
123
124            if (numAliveState == 1 && acc_.GetOpCode(acc_.GetState(gate)) == OpCode::LOOP_BEGIN) {
125                result.SetFieldValue(field, value);
126            } else if (numAliveState < numIn) {
127                result.SetFieldValue(field, Circuit::NullGate());
128            } else {
129                if (!differentFlag) {
130                    result.SetFieldValue(field, value);
131                } else {
132                    State& oldState = escapeAnalysis_->GetOrCreateState(gate);
133                    GateRef oldValue = oldState.GetFieldValue(field);
134                    if (oldValue != Circuit::NullGate() &&
135                        acc_.GetOpCode(oldValue) == OpCode::DEPEND_SELECTOR &&
136                        acc_.GetState(oldValue) == acc_.GetState(gate)) {
137                        for (size_t i = 0; i < numIn; i++) {
138                            ASSERT(input[i + 1] != Circuit::NullGate());
139                            if (acc_.GetValueIn(oldValue, i) != input[i + 1]) {
140                                acc_.ReplaceValueIn(oldValue, input[i + 1], i);
141                                escapeAnalysis_->RevisitGate(oldValue);
142                            }
143                        }
144                        result.SetFieldValue(field, oldValue);
145                    } else {
146                        MachineType machineType = acc_.GetMachineType(value);
147                        auto gateType = acc_.GetGateType(value);
148                        const GateMetaData* meta = circuit_->ValueSelector(numIn);
149                        GateRef valueSelector = circuit_->NewGate(meta, machineType, input.size(),
150                                                                  input.data(), gateType);
151                        result.SetFieldValue(field, valueSelector);
152                        escapeAnalysis_->RevisitGate(valueSelector);
153                    }
154                }
155            }
156        }
157    }
158    return result;
159}
160
161GateRef GateInfo::GetFieldValue(FieldLocation field) const
162{
163    return state_.GetFieldValue(field);
164}
165
166void GateInfo::SetFieldValue(FieldLocation field, GateRef value)
167{
168    state_.SetFieldValue(field, value);
169}
170
171void GateInfo::SetEliminated()
172{
173    replacement_ = circuit_->DeadGate();
174    object_ = nullptr;
175}
176
177void GateInfo::SetReplacement(GateRef replacement)
178{
179    replacement_ = replacement;
180    object_ = escapeAnalysis_->TryGetVirtualObject(replacement);
181}
182
183void GateInfo::SetVirtualObject(VirtualObject* object)
184{
185    object_ = object;
186}
187
188void State::SetFieldValue(FieldLocation field, GateRef gate)
189{
190    map_[field] = gate;
191}
192
193GateRef State::GetFieldValue(FieldLocation field) const
194{
195    auto result = map_.find(field);
196    if (result == map_.end()) {
197        return Circuit::NullGate();
198    }
199    return result->second;
200}
201
202bool State::IsMapEqual(const State &state) const
203{
204    return map_.size() == state.map_.size() &&
205           std::equal(map_.begin(), map_.end(), state.map_.begin());
206}
207
208void EscapeAnalysis::SetReplacement(GateRef gate, GateRef replacement)
209{
210    replacements_[gate] = replacement;
211}
212
213GateRef EscapeAnalysis::TryGetReplacement(GateRef gate) const
214{
215    if (!replacements_.count(gate)) {
216        return Circuit::NullGate();
217    }
218    return replacements_.at(gate);
219}
220
221GateRef EscapeAnalysis::GetCurrentGate(GateRef gate) const
222{
223    GateRef replacement = TryGetReplacement(gate);
224    if (replacement == Circuit::NullGate()) {
225        return gate;
226    }
227    return replacement;
228}
229
230VirtualObject* EscapeAnalysis::TryGetVirtualObject(GateRef gate) const
231{
232    if (gateToVirtualObject_.count(gate)) {
233        VirtualObject* vObj = gateToVirtualObject_.at(gate);
234        return vObj;
235    }
236    return nullptr;
237}
238
239VirtualObject* EscapeAnalysis::TryGetVirtualObjectAndAddUser(GateRef gate, GateRef currentGate)
240{
241    if (gateToVirtualObject_.count(gate)) {
242        VirtualObject* vObj = gateToVirtualObject_[gate];
243        if (vObj != nullptr) {
244            vObj->AddUser(currentGate);
245        }
246        return vObj;
247    }
248    return nullptr;
249}
250
251
252void EscapeAnalysis::SetVirtualObject(GateRef gate, VirtualObject* object)
253{
254    gateToVirtualObject_[gate] = object;
255}
256
257void EscapeAnalysis::RevisitUser(VirtualObject* vObj)
258{
259    auto& users = vObj->GetUsers();
260    for (auto user : users) {
261        if (isTraced_) {
262            LOG_COMPILER(INFO) << "[escape analysis] revisit user : " <<acc_.GetId(user);
263        }
264        visitor_->ReVisitGate(user);
265    }
266    vObj->ClearUsers();
267}
268
269void EscapeAnalysis::SetEscaped(GateRef gate)
270{
271    if (isTraced_) {
272        LOG_COMPILER(INFO) << "[escape analysis] set escaped: " << acc_.GetId(gate);
273    }
274    VirtualObject* vObj = TryGetVirtualObject(gate);
275    if (vObj != nullptr && !vObj->IsEscaped()) {
276        vObj->SetEscaped();
277        RevisitUser(vObj);
278    }
279}
280
281VirtualObject* EscapeAnalysis::GetOrCreateVirtualObject(size_t numIn, GateInfo* info)
282{
283    GateRef gate = info->GetCurrentGate();
284    VirtualObject* vobj = TryGetVirtualObject(gate);
285    if (vobj == nullptr) {
286        vobj = chunk_->New<VirtualObject>(numIn, chunk_);
287    }
288    vobj->AddUser(gate);
289    info->SetVirtualObject(vobj);
290    return vobj;
291}
292
293
294GateRef EscapeAnalysis::VisitCreateObjectWithBuffer(GateRef gate, GateInfo* info)
295{
296    constexpr size_t startIn = 4; // 4 : start of props
297    constexpr size_t fieldSize = 8; // 8 : bytes per field
298    constexpr size_t stride = 2; // 2: offset and value
299    auto numIn = acc_.GetNumValueIn(gate);
300    size_t size = acc_.GetConstantValue(acc_.GetValueIn(gate, 0)) / fieldSize;
301    VirtualObject* vObj = GetOrCreateVirtualObject(size, info);
302
303    for (size_t i = startIn; i < numIn; i += stride) {
304        GateRef value = acc_.GetValueIn(gate, i);
305        GateRef offset = acc_.GetValueIn(gate, i + 1);
306        if (vObj != nullptr && !vObj->IsEscaped() &&
307            vObj->GetField(acc_.GetConstantValue(offset)) != FieldLocation::Invalid()) {
308            info->SetFieldValue(vObj->GetField(acc_.GetConstantValue(offset)), value);
309        } else {
310            SetEscaped(value);
311            SetEscaped(gate);
312        }
313    }
314    info->SetVirtualObject(vObj);
315    return replaceGate_;
316}
317
318GateRef EscapeAnalysis::VisitLoadProperty(GateRef gate, GateInfo* info)
319{
320    GateRef object = acc_.GetValueIn(gate, 0);
321    GateRef offset = acc_.GetValueIn(gate, 1);
322    VirtualObject* vObj = TryGetVirtualObjectAndAddUser(object, gate);
323
324    PropertyLookupResult plr(acc_.GetConstantValue(offset));
325
326    if (vObj != nullptr && !vObj->IsEscaped() && vObj->GetField(plr.GetOffset()) != FieldLocation::Invalid()) {
327        GateRef value = info->GetFieldValue(vObj->GetField(plr.GetOffset()));
328        if (value != Circuit::NullGate()) {
329            if (isTraced_) {
330                LOG_COMPILER(INFO) << "[escape analysis] replace" << acc_.GetId(gate) << " with " << acc_.GetId(value);
331            }
332            info->SetReplacement(value);
333        } else {
334            SetEscaped(object);
335        }
336    } else {
337        SetEscaped(object);
338    }
339    return replaceGate_;
340}
341
342GateRef EscapeAnalysis::VisitLoadConstOffset(GateRef gate, GateInfo* info)
343{
344    GateRef object = acc_.GetValueIn(gate, 0);
345    size_t offset = acc_.GetOffset(gate);
346    VirtualObject* vObj = TryGetVirtualObjectAndAddUser(object, gate);
347
348    if (vObj != nullptr && !vObj->IsEscaped() && vObj->GetField(offset) != FieldLocation::Invalid()) {
349        GateRef value = info->GetFieldValue(vObj->GetField(offset));
350        if (value != Circuit::NullGate()) {
351            if (isTraced_) {
352                LOG_COMPILER(INFO) << "[escape analysis] replace " <<
353                                      acc_.GetId(gate) << " with " << acc_.GetId(value);
354            }
355            info->SetReplacement(value);
356        } else {
357            SetEscaped(object);
358        }
359    } else {
360        SetEscaped(object);
361    }
362    return replaceGate_;
363}
364
365
366GateRef EscapeAnalysis::VisitStoreProperty(GateRef gate, GateInfo* info)
367{
368    GateRef object = acc_.GetValueIn(gate, 0);
369    GateRef offset = acc_.GetValueIn(gate, 1);
370    GateRef value = acc_.GetValueIn(gate, 2);
371    VirtualObject* vObj = TryGetVirtualObjectAndAddUser(object, gate);
372    PropertyLookupResult plr(acc_.GetConstantValue(offset));
373
374    if (vObj != nullptr && !vObj->IsEscaped() && vObj->GetField(plr.GetOffset()) != FieldLocation::Invalid()) {
375        info->SetFieldValue(vObj->GetField(plr.GetOffset()), value);
376        info->SetEliminated();
377    } else {
378        SetEscaped(value);
379        SetEscaped(object);
380    }
381    return replaceGate_;
382}
383
384GateRef EscapeAnalysis::VisitObjectTypeCheck(GateRef gate, GateInfo* info)
385{
386    info->SetVirtualObject(TryGetVirtualObject(acc_.GetValueIn(gate)));
387    return Circuit::NullGate();
388}
389
390State& EscapeAnalysis::GetOrCreateState(GateRef gate)
391{
392    auto it = gateToState_.find(gate);
393    if (it == gateToState_.end()) {
394        State tmp(chunk_);
395        auto result = gateToState_.insert(std::make_pair(gate, std::move(tmp)));
396        return result.first->second;
397    }
398    return it->second;
399}
400
401void EscapeAnalysis::SetState(GateRef gate, State state)
402{
403    auto it = gateToState_.find(gate);
404    if (it == gateToState_.end()) {
405        gateToState_.insert(std::make_pair(gate, std::move(state)));
406    } else {
407        it->second = state;
408    }
409}
410
411void EscapeAnalysis::RevisitGate(GateRef gate)
412{
413    visitor_->ReVisitGate(gate);
414}
415
416void EscapeAnalysis::SetReplaceGate(GateRef gate)
417{
418    replaceGate_ = gate;
419}
420
421GateRef EscapeAnalysis::VisitGate(GateRef gate)
422{
423    GateInfo info(circuit_, gate, this, chunk_);
424    auto opcode = acc_.GetOpCode(gate);
425    replaceGate_ = Circuit::NullGate();
426    switch (opcode) {
427        case OpCode::STORE_PROPERTY:
428        case OpCode::STORE_PROPERTY_NO_BARRIER:
429            return VisitStoreProperty(gate, &info);
430        case OpCode::LOAD_PROPERTY:
431            return VisitLoadProperty(gate, &info);
432        case OpCode::LOAD_CONST_OFFSET:
433            return VisitLoadConstOffset(gate, &info);
434        case OpCode::TYPED_CREATE_OBJ_WITH_BUFFER:
435            return VisitCreateObjectWithBuffer(gate, &info);
436        case OpCode::OBJECT_TYPE_CHECK:
437        case OpCode::CHECK_AND_CONVERT:
438            return VisitObjectTypeCheck(gate, &info);
439        case OpCode::FRAME_VALUES:
440        case OpCode::STATE_SPLIT:
441        case OpCode::FRAME_STATE:
442            break;
443        default : {
444            size_t numIns = acc_.GetNumValueIn(gate);
445            for (size_t i = 0; i < numIns; i++) {
446                GateRef in = GetCurrentGate(acc_.GetValueIn(gate, i));
447                SetEscaped(in);
448            }
449        }
450    }
451    return Circuit::NullGate();
452}
453
454}