1 /*
2 * Copyright (c) 2025 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 "astNodeHistory.h"
17 #include "compiler/lowering/phase.h"
18
19 namespace ark::es2panda::ir {
20
AstNodeHistory(AstNode * node,int32_t phaseId,ArenaAllocator * allocator)21 AstNodeHistory::AstNodeHistory(AstNode *node, int32_t phaseId, ArenaAllocator *allocator) : list_ {allocator}
22 {
23 Set(node, phaseId);
24 }
25
FindBackwardEquals(int32_t phaseId)26 AstNode *AstNodeHistory::FindBackwardEquals(int32_t phaseId)
27 {
28 auto item = item_;
29
30 while ((item = item->prev) != nullptr) {
31 if (LIKELY(item->data.phaseId == phaseId)) {
32 item_ = item;
33 return item->data.node;
34 }
35 }
36
37 return nullptr;
38 }
39
FindForwardEquals(int32_t phaseId)40 AstNode *AstNodeHistory::FindForwardEquals(int32_t phaseId)
41 {
42 auto item = item_;
43
44 do {
45 if (LIKELY(item->data.phaseId == phaseId)) {
46 item_ = item;
47 return item->data.node;
48 }
49 } while ((item = item->next) != nullptr);
50
51 return nullptr;
52 }
53
54 // Find node state precisely at phase with a given ID
55 // (e.g. find the node history record with `phaseId` equal to a given value)
At(int32_t phaseId)56 AstNode *AstNodeHistory::At(int32_t phaseId)
57 {
58 if (LIKELY(item_->data.phaseId == phaseId)) {
59 // Start searching with last accessed item
60 // In most cases last accessed item is the one we are looking for
61 return item_->data.node;
62 }
63 if (LIKELY(item_->data.phaseId > phaseId)) {
64 // Search backwards starting at last accessed node for the node at previous phase
65 return FindBackwardEquals(phaseId);
66 }
67 // Search forward starting at last accessed node for the node at next phase
68 return FindForwardEquals(phaseId);
69 }
70
71 // Find node state at phase with a given ID
72 // (e.g. find last node history record with `phaseId` less or equal to a given value)
Get(int32_t phaseId)73 AstNode *AstNodeHistory::Get(int32_t phaseId)
74 {
75 auto found = FindLessOrEquals(phaseId);
76 if (LIKELY(found != nullptr)) {
77 item_ = found;
78 return item_->data.node;
79 }
80
81 return nullptr;
82 }
83
84 // Find node state at phase with a given ID and set its new value, insert new history record if not found
Set(AstNode * node,int32_t phaseId)85 void AstNodeHistory::Set(AstNode *node, int32_t phaseId)
86 {
87 HistoryRecord record {node, phaseId};
88 if (LIKELY(list_.Empty() || list_.Tail()->data.phaseId < phaseId)) {
89 item_ = list_.Append(record);
90 } else if (list_.Head()->data.phaseId > phaseId) {
91 item_ = list_.Prepend(record);
92 } else if (auto found = FindLessOrEquals(phaseId); found != nullptr) {
93 if (found->data.phaseId == phaseId) {
94 item_ = found;
95 item_->data.node = node;
96 } else {
97 item_ = list_.Insert(found, record);
98 ES2PANDA_ASSERT(item_->prev->data.phaseId < item_->data.phaseId &&
99 item_->data.phaseId < item_->next->data.phaseId);
100 }
101 } else {
102 ES2PANDA_UNREACHABLE();
103 }
104 }
105
106 // Find node state at phase with a given ID
107 // (e.g. find last node history record with `phaseId` less or equal to a given value)
FindLessOrEquals(int32_t phaseId)108 AstNodeHistory::HistoryList::Item *AstNodeHistory::FindLessOrEquals(int32_t phaseId)
109 {
110 // Start searching with last accessed item
111 auto item = item_;
112
113 if (LIKELY(item->data.phaseId == phaseId)) {
114 // In most cases last accessed item is the one we are looking for
115 return item;
116 }
117 if (LIKELY(item->data.phaseId > phaseId)) {
118 // Search backwards starting at last accessed node for the node at previous phase
119 while ((item = item->prev) != nullptr) {
120 if (item->data.phaseId <= phaseId) {
121 return item;
122 }
123 }
124 } else {
125 // Search forward starting at last accessed node for the node at next phase
126 while (item->next != nullptr) {
127 if (item->data.phaseId == phaseId) {
128 return item;
129 }
130 if (item->data.phaseId > phaseId && item->prev != nullptr) {
131 item = item->prev;
132 return item;
133 }
134 item = item->next;
135 }
136 if (item->data.phaseId <= phaseId) {
137 return item;
138 }
139 }
140
141 return nullptr;
142 }
143 } // namespace ark::es2panda::ir
144