1 /*
2 * Copyright (c) 2021 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/verifier.h"
17
18 #include <cmath>
19 #include <stack>
20 #include <string>
21 #include <unordered_set>
22 #include <vector>
23
24 #include "ecmascript/compiler/share_gate_meta_data.h"
25 #include "ecmascript/compiler/scheduler.h"
26 #include "ecmascript/compiler/gate_accessor.h"
27 #include "ecmascript/ecma_macros.h"
28 #include "ecmascript/log_wrapper.h"
29
30 namespace panda::ecmascript::kungfu {
RunDataIntegrityCheck(const Circuit * circuit)31 bool Verifier::RunDataIntegrityCheck(const Circuit *circuit)
32 {
33 std::unordered_set<GateRef> gatesSet;
34 std::vector<GateRef> gatesList;
35 GateRef prevGate = sizeof(Out);
36 gatesList.push_back(prevGate);
37 gatesSet.insert(prevGate);
38 size_t out = Gate::GetGateSize(0);
39 while (true) {
40 GateRef gate = circuit->GetGateRef(
41 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
42 reinterpret_cast<const Out *>(circuit->LoadGatePtrConst(GateRef(out)))->GetGateConst());
43 if (gate < prevGate + static_cast<int64_t>(sizeof(Gate)) ||
44 gate >= static_cast<int64_t>(circuit->GetCircuitDataSize())) {
45 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (bad next gate)";
46 LOG_COMPILER(ERROR) << "at: " << std::dec << gate;
47 return false;
48 }
49 gatesList.push_back(gate);
50 gatesSet.insert(gate);
51 prevGate = gate;
52 out += Gate::GetGateSize(
53 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
54 reinterpret_cast<const Out *>(circuit->LoadGatePtrConst(GateRef(out)))->GetIndex() + 1);
55 if (out == circuit->GetCircuitDataSize()) {
56 break;
57 }
58 if (out > circuit->GetCircuitDataSize() || out < 0) {
59 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (out of bound access)";
60 LOG_COMPILER(ERROR) << "at: " << std::dec << out;
61 return false;
62 }
63 }
64 for (const auto &gate : gatesList) {
65 for (size_t idx = 0; idx < circuit->LoadGatePtrConst(gate)->GetNumIns(); idx++) {
66 const In *curIn = circuit->LoadGatePtrConst(gate)->GetInConst(idx);
67 if (!(circuit->GetSpaceDataStartPtrConst() < curIn && curIn < circuit->GetSpaceDataEndPtrConst())) {
68 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (corrupted in list)";
69 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
70 return false;
71 }
72 if (gatesSet.count(circuit->GetGateRef(curIn->GetGateConst())) == 0) {
73 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (invalid in address)";
74 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
75 return false;
76 }
77 }
78 {
79 const Gate *curGate = circuit->LoadGatePtrConst(gate);
80 if (!curGate->IsFirstOutNull()) {
81 const Out *curOut = curGate->GetFirstOutConst();
82 if (!(circuit->GetSpaceDataStartPtrConst() < curOut && curOut < circuit->GetSpaceDataEndPtrConst())) {
83 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (corrupted out list)";
84 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
85 return false;
86 }
87 if (gatesSet.count(circuit->GetGateRef(curOut->GetGateConst())) == 0) {
88 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (invalid out address)";
89 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
90 return false;
91 }
92 while (!curOut->IsNextOutNull()) {
93 curOut = curOut->GetNextOutConst();
94 if (!(circuit->GetSpaceDataStartPtrConst() < curOut &&
95 curOut < circuit->GetSpaceDataEndPtrConst())) {
96 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (corrupted out list)";
97 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
98 return false;
99 }
100 if (gatesSet.count(circuit->GetGateRef(curOut->GetGateConst())) == 0) {
101 LOG_COMPILER(ERROR) << "[Verifier][Error] Circuit data is corrupted (invalid out address)";
102 LOG_COMPILER(ERROR) << "id: " << std::dec << circuit->GetId(gate);
103 return false;
104 }
105 }
106 }
107 }
108 }
109 return true;
110 }
111
RunStateGatesCheck(const Circuit * circuit,const std::vector<GateRef> & bbGatesList,const std::string & methodName)112 bool Verifier::RunStateGatesCheck(const Circuit *circuit, const std::vector<GateRef> &bbGatesList,
113 const std::string& methodName)
114 {
115 for (const auto &bbGate : bbGatesList) {
116 circuit->Verify(bbGate, methodName);
117 }
118 return true;
119 }
120
RunCFGSoundnessCheck(const Circuit * circuit,const std::vector<GateRef> & bbGatesList,const std::unordered_map<GateRef,size_t> & bbGatesAddrToIdx)121 bool Verifier::RunCFGSoundnessCheck(const Circuit *circuit, const std::vector<GateRef> &bbGatesList,
122 const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx)
123 {
124 for (const auto &bbGate : bbGatesList) {
125 GateAccessor gateAcc(const_cast<Circuit *>(circuit));
126 for (const auto &predGate : gateAcc.ConstIns(bbGate)) {
127 if (gateAcc.IsState(predGate) || circuit->GetOpCode(predGate) == OpCode::STATE_ENTRY) {
128 if (bbGatesAddrToIdx.count(predGate) == 0) {
129 LOG_COMPILER(ERROR) << "[Verifier][Error] CFG is not sound";
130 LOG_COMPILER(ERROR) << "Proof:";
131 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(predGate) << ") is pred of "
132 << "(id=" << circuit->GetId(bbGate) << ")";
133 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(bbGate) << ") is reachable from entry";
134 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(predGate) << ") is unreachable from entry";
135 return false;
136 }
137 }
138 }
139 }
140 return true;
141 }
142
RunCFGIsDAGCheck(const Circuit * circuit)143 bool Verifier::RunCFGIsDAGCheck(const Circuit *circuit)
144 {
145 circuit->AdvanceTime();
146 struct DFSState {
147 GateRef cur;
148 GateAccessor::ConstUseWrapper uses;
149 GateAccessor::ConstUseIterator use;
150 };
151 std::stack<DFSState> dfsStack;
152 GateAccessor gateAcc(const_cast<Circuit *>(circuit));
153 auto root = gateAcc.GetStateRoot();
154 gateAcc.SetVisited(root);
155 auto rootUses = gateAcc.ConstUses(root);
156 dfsStack.push({root, rootUses, rootUses.begin()});
157 while (!dfsStack.empty()) {
158 auto &curState = dfsStack.top();
159 auto &cur = curState.cur;
160 auto &uses = curState.uses;
161 auto &use = curState.use;
162 if (use == uses.end()) {
163 gateAcc.SetFinished(cur);
164 dfsStack.pop();
165 continue;
166 }
167 if (gateAcc.IsState(*use) && use.GetIndex() < gateAcc.GetStateCount(*use)) {
168 if (gateAcc.IsVisited(*use)) {
169 LOG_COMPILER(ERROR) <<
170 "[Verifier][Error] CFG without loop back edges is not a directed acyclic graph";
171 LOG_COMPILER(ERROR) << "Proof:";
172 LOG_COMPILER(ERROR) << "(id=" << gateAcc.GetId(*use) << ") is succ of "
173 << "(id=" << gateAcc.GetId(cur) << ")";
174 LOG_COMPILER(ERROR) << "(id=" << gateAcc.GetId(cur) << ") is reachable from "
175 << "(id=" << gateAcc.GetId(*use) << ") without loop back edges";
176 return false;
177 }
178 if (gateAcc.IsFinished(*use) || gateAcc.IsLoopBack(*use)) {
179 ++use;
180 continue;
181 }
182 gateAcc.SetVisited(*use);
183 auto newUses = gateAcc.ConstUses(*use);
184 dfsStack.push({*use, newUses, newUses.begin()});
185 }
186 ++use;
187 }
188 return true;
189 }
190
RunCFGReducibilityCheck(const Circuit * circuit,const std::vector<GateRef> & bbGatesList,const std::unordered_map<GateRef,size_t> & bbGatesAddrToIdx,const std::function<bool (size_t,size_t)> & isAncestor)191 bool Verifier::RunCFGReducibilityCheck(const Circuit *circuit, const std::vector<GateRef> &bbGatesList,
192 const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
193 const std::function<bool(size_t, size_t)> &isAncestor)
194 {
195 for (const auto &curGate : bbGatesList) {
196 if (circuit->GetOpCode(curGate) == OpCode::LOOP_BACK) {
197 GateAccessor gateAcc(const_cast<Circuit *>(circuit));
198 auto uses = gateAcc.ConstUses(curGate);
199 for (auto use = uses.begin(); use != uses.end(); use++) {
200 if (use.GetIndex() >= circuit->LoadGatePtrConst(*use)->GetStateCount()) {
201 continue;
202 }
203 ASSERT(gateAcc.IsState(*use));
204 bool isDom = isAncestor(bbGatesAddrToIdx.at(*use), bbGatesAddrToIdx.at(curGate));
205 if (!isDom) {
206 LOG_COMPILER(ERROR) << "[Verifier][Error] CFG is not reducible";
207 LOG_COMPILER(ERROR) << "Proof:";
208 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(*use) << ") is loop back succ of "
209 << "(id=" << circuit->GetId(curGate) << ")";
210 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(*use) << ") does not dominate "
211 << "(id=" << circuit->GetId(curGate) << ")";
212 return false;
213 }
214 }
215 }
216 }
217 return true;
218 }
219
RunFixedGatesCheck(const Circuit * circuit,const std::vector<GateRef> & fixedGatesList)220 bool Verifier::RunFixedGatesCheck(const Circuit *circuit, const std::vector<GateRef> &fixedGatesList)
221 {
222 for (const auto &fixedGate : fixedGatesList) {
223 circuit->Verify(fixedGate);
224 }
225 return true;
226 }
227
RunFixedGatesRelationsCheck(const Circuit * circuit,const std::vector<GateRef> & fixedGatesList,const std::unordered_map<GateRef,size_t> & bbGatesAddrToIdx,const std::function<bool (size_t,size_t)> & isAncestor)228 bool Verifier::RunFixedGatesRelationsCheck(const Circuit *circuit, const std::vector<GateRef> &fixedGatesList,
229 const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
230 const std::function<bool(size_t, size_t)> &isAncestor)
231 {
232 ConstGateAccessor ac(circuit);
233 for (const auto &fixedGate : fixedGatesList) {
234 size_t cnt = 0;
235 auto ins = ac.Ins(fixedGate);
236 for (auto i = ins.begin(); i != ins.end(); i++) {
237 GateRef predGate = *i;
238 if (ac.IsFixed(predGate) &&
239 // 2: Judge equality
240 (circuit->GetOpCode(circuit->GetIn(fixedGate, 0)) == OpCode::LOOP_BEGIN && cnt == 2)) {
241 ASSERT(cnt > 0);
242 auto a = bbGatesAddrToIdx.at(circuit->GetIn(predGate, 0));
243 auto b = bbGatesAddrToIdx.at(circuit->GetIn(circuit->GetIn(fixedGate, 0),
244 static_cast<size_t>(cnt - 1)));
245 if (!isAncestor(a, b)) {
246 LOG_COMPILER(ERROR) << "[Verifier][Error] Fixed gates relationship is not consistent";
247 LOG_COMPILER(ERROR) << "Proof:";
248 LOG_COMPILER(ERROR) << "Fixed gate (id="
249 << circuit->GetId(predGate)
250 << ") is pred of fixed gate (id="
251 << circuit->GetId(fixedGate) << ")";
252 LOG_COMPILER(ERROR) << "BB_" << bbGatesAddrToIdx.at(circuit->GetIn(predGate, 0))
253 << " does not dominate BB_"
254 << bbGatesAddrToIdx.at(circuit->GetIn(circuit->GetIn(fixedGate, 0),
255 static_cast<size_t>(cnt - 1)));
256 return false;
257 }
258 }
259 cnt++;
260 }
261 }
262 return true;
263 }
264
RunFlowCyclesFind(const Circuit * circuit,std::vector<GateRef> * schedulableGatesListPtr,const std::vector<GateRef> & bbGatesList,const std::vector<GateRef> & fixedGatesList)265 bool Verifier::RunFlowCyclesFind(const Circuit *circuit, std::vector<GateRef> *schedulableGatesListPtr,
266 const std::vector<GateRef> &bbGatesList, const std::vector<GateRef> &fixedGatesList)
267 {
268 circuit->AdvanceTime();
269 ConstGateAccessor ac(circuit);
270 std::vector<GateRef> startGateList;
271 for (const auto &gate : bbGatesList) {
272 auto ins = ac.Ins(gate);
273 for (auto i = ins.begin(); i != ins.end(); i++) {
274 GateRef predGate = *i;
275 if (ac.IsSchedulable(predGate)) {
276 if (circuit->GetMark(predGate) == MarkCode::NO_MARK) {
277 startGateList.push_back(predGate);
278 circuit->SetMark(predGate, MarkCode::VISITED);
279 }
280 }
281 }
282 }
283 for (const auto &gate : fixedGatesList) {
284 auto ins = ac.Ins(gate);
285 for (auto i = ins.begin(); i != ins.end(); i++) {
286 GateRef predGate = *i;
287 if (ac.IsSchedulable(predGate)) {
288 if (circuit->GetMark(predGate) == MarkCode::NO_MARK) {
289 startGateList.push_back(predGate);
290 circuit->SetMark(predGate, MarkCode::VISITED);
291 }
292 }
293 }
294 }
295 circuit->AdvanceTime();
296 GateAccessor gateAcc(const_cast<Circuit *>(circuit));
297 std::vector<GateRef> cycleGatesList;
298 GateRef meet = -1;
299 struct DFSState {
300 GateRef cur;
301 size_t numIns;
302 size_t idx;
303 };
304 for (const auto &startGate : startGateList) {
305 if (!gateAcc.IsNotMarked(startGate)) {
306 continue;
307 }
308 std::stack<DFSState> dfsStack;
309 size_t startNumIns = gateAcc.GetNumIns(startGate);
310 dfsStack.push({startGate, startNumIns, 0});
311 gateAcc.SetVisited(startGate);
312 schedulableGatesListPtr->push_back(startGate);
313 while (!dfsStack.empty()) {
314 auto &curState = dfsStack.top();
315 auto &cur = curState.cur;
316 auto &numIns = curState.numIns;
317 auto &idx = curState.idx;
318 if (idx == numIns) {
319 gateAcc.SetFinished(cur);
320 dfsStack.pop();
321 continue;
322 }
323 const auto prev = gateAcc.GetIn(cur, idx);
324 if (gateAcc.IsSchedulable(prev)) {
325 if (gateAcc.IsVisited(prev)) {
326 LOG_COMPILER(ERROR) <<
327 "[Verifier][Error] Found a data or depend flow cycle without passing selectors";
328 LOG_COMPILER(ERROR) << "Proof:";
329 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(prev) << ") is prev of "
330 << "(id=" << circuit->GetId(cur) << ")";
331 LOG_COMPILER(ERROR) << "(id=" << circuit->GetId(prev) << ") is reachable from "
332 << "(id=" << circuit->GetId(cur) << ") without passing selectors";
333 meet = prev;
334 break;
335 }
336 if (!gateAcc.IsFinished(prev)) {
337 size_t newNumIns = gateAcc.GetNumIns(prev);
338 dfsStack.push({prev, newNumIns, 0});
339 gateAcc.SetVisited(prev);
340 schedulableGatesListPtr->push_back(prev);
341 }
342 }
343 idx++;
344 }
345 if (meet != -1) {
346 while (dfsStack.top().cur != meet) {
347 cycleGatesList.push_back(dfsStack.top().cur);
348 dfsStack.pop();
349 }
350 cycleGatesList.push_back(meet);
351 LOG_COMPILER(ERROR) << "Path:";
352 for (const auto &cycleGate : cycleGatesList) {
353 gateAcc.Print(cycleGate);
354 }
355 return false;
356 }
357 }
358 return true;
359 }
360
RunSchedulableGatesCheck(const Circuit * circuit,const std::vector<GateRef> & schedulableGatesList)361 bool Verifier::RunSchedulableGatesCheck(const Circuit *circuit, const std::vector<GateRef> &schedulableGatesList)
362 {
363 for (const auto &schedulableGate : schedulableGatesList) {
364 circuit->Verify(schedulableGate);
365 }
366 return true;
367 }
368
RunPrologGatesCheck(const Circuit * circuit,const std::vector<GateRef> & schedulableGatesList)369 bool Verifier::RunPrologGatesCheck(const Circuit *circuit, const std::vector<GateRef> &schedulableGatesList)
370 {
371 ConstGateAccessor ac(circuit);
372 for (const auto &schedulableGate : schedulableGatesList) {
373 auto ins = ac.Ins(schedulableGate);
374 for (auto i = ins.begin(); i != ins.end(); i++) {
375 GateRef r = *i;
376 if (ac.IsProlog(r)) {
377 circuit->Verify(r);
378 }
379 }
380 }
381 return true;
382 }
383
RunSchedulingBoundsCheck(const Circuit * circuit,const std::vector<GateRef> & schedulableGatesList,const std::unordered_map<GateRef,size_t> & bbGatesAddrToIdx,const std::function<bool (size_t,size_t)> & isAncestor,const std::function<size_t (size_t,size_t)> & lowestCommonAncestor)384 bool Verifier::RunSchedulingBoundsCheck(const Circuit *circuit,
385 const std::vector<GateRef> &schedulableGatesList,
386 const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
387 const std::function<bool(size_t, size_t)> &isAncestor,
388 const std::function<size_t(size_t, size_t)> &lowestCommonAncestor)
389 {
390 // check existence of scheduling upper bound
391 std::unordered_map<GateRef, size_t> upperBound;
392 {
393 if (!Scheduler::CalculateSchedulingUpperBound(circuit, bbGatesAddrToIdx, isAncestor,
394 schedulableGatesList, upperBound)) {
395 return false;
396 }
397 }
398 // check existence of scheduling lower bound
399 std::unordered_map<GateRef, size_t> lowerBound;
400 {
401 Scheduler::CalculateSchedulingLowerBound(circuit, bbGatesAddrToIdx, lowestCommonAncestor, lowerBound);
402 }
403 // check consistency of lower bound and upper bound
404 {
405 ASSERT(upperBound.size() == lowerBound.size());
406 for (const auto &item : lowerBound) {
407 if (!isAncestor(upperBound.at(item.first), lowerBound.at(item.first))) {
408 LOG_COMPILER(ERROR) << "[Verifier][Error] Bounds of gate (id="
409 << circuit->GetId(item.first) << ") is not consistent";
410 LOG_COMPILER(ERROR) << "Proof:";
411 LOG_COMPILER(ERROR) << "Upper bound is BB_" << upperBound.at(item.first);
412 LOG_COMPILER(ERROR) << "Lower bound is BB_" << lowerBound.at(item.first);
413 return false;
414 }
415 }
416 }
417 return true;
418 }
419
FindFixedGates(const Circuit * circuit,const std::vector<GateRef> & bbGatesList,std::vector<GateRef> & fixedGatesList)420 void Verifier::FindFixedGates(const Circuit *circuit, const std::vector<GateRef> &bbGatesList,
421 std::vector<GateRef> &fixedGatesList)
422 {
423 ConstGateAccessor ac(circuit);
424 for (const auto &bbGate : bbGatesList) {
425 for (const auto &succGate : circuit->GetOutVector(bbGate)) {
426 if (ac.IsFixed(succGate)) {
427 fixedGatesList.push_back(succGate);
428 }
429 }
430 }
431 }
432
RunFlowCyclesFind(const Circuit * circuit)433 bool Verifier::RunFlowCyclesFind(const Circuit* circuit)
434 {
435 GateAccessor acc(const_cast<Circuit *>(circuit));
436 circuit->AdvanceTime();
437 struct DFSStack {
438 GateRef gate;
439 GateAccessor::UseIterator it;
440 GateAccessor::UseIterator end;
441 };
442 std::stack<DFSStack> st;
443 auto root = acc.GetCircuitRoot();
444 auto rootUse = acc.Uses(root);
445 st.push({root, rootUse.begin(), rootUse.end()});
446 acc.SetVisited(root);
447 while (!st.empty()) {
448 auto& cur = st.top();
449 if (cur.it == cur.end) {
450 st.pop();
451 acc.SetFinished(cur.gate);
452 continue;
453 }
454 auto succ = *cur.it;
455 if (acc.IsLoopBackUse(cur.gate, cur.it)) {
456 cur.it++;
457 continue;
458 }
459 if (acc.IsNotMarked(succ)) {
460 auto succUse = acc.Uses(succ);
461 st.push({succ, succUse.begin(), succUse.end()});
462 acc.SetVisited(succ);
463 } else if (acc.IsVisited(succ)) {
464 LOG_COMPILER(ERROR) << "====================== Cycle Found ======================";
465 std::string log = "";
466 while (st.top().gate != succ) {
467 log += std::to_string(acc.GetId(st.top().gate)) + " < ";
468 st.pop();
469 }
470 log += std::to_string(acc.GetId(st.top().gate));
471 LOG_COMPILER(ERROR) << log;
472 return true;
473 }
474 cur.it++;
475 }
476 return false;
477 }
478
Run(const Circuit * circuit,const std::string & methodName,bool enableLog)479 bool Verifier::Run(const Circuit *circuit, const std::string& methodName, bool enableLog)
480 {
481 if (!RunDataIntegrityCheck(circuit)) {
482 if (enableLog) {
483 LOG_COMPILER(ERROR) << "[Verifier][Fail] Circuit data integrity verifier failed, " << methodName;
484 }
485 return false;
486 }
487 std::vector<GateRef> bbGatesList;
488 std::unordered_map<GateRef, size_t> bbGatesAddrToIdx;
489 std::vector<size_t> immDom;
490 Scheduler::CalculateDominatorTree(circuit, bbGatesList, bbGatesAddrToIdx, immDom);
491 if (!RunStateGatesCheck(circuit, bbGatesList, methodName)) {
492 if (enableLog) {
493 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunStateGatesCheck failed";
494 }
495 return false;
496 }
497 if (!RunCFGSoundnessCheck(circuit, bbGatesList, bbGatesAddrToIdx)) {
498 if (enableLog) {
499 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunCFGSoundnessCheck failed";
500 }
501 return false;
502 }
503 if (!RunCFGIsDAGCheck(circuit)) {
504 if (enableLog) {
505 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunCFGIsDAGCheck failed";
506 }
507 return false;
508 }
509 std::vector<std::vector<size_t>> sonList(bbGatesList.size());
510 for (size_t idx = 1; idx < immDom.size(); idx++) {
511 sonList[immDom[idx]].push_back(idx);
512 }
513 const size_t sizeLog = std::ceil(std::log2(static_cast<double>(bbGatesList.size())) + 1);
514 std::vector<size_t> timeIn(bbGatesList.size());
515 std::vector<size_t> timeOut(bbGatesList.size());
516 std::vector<std::vector<size_t>> jumpUp;
517 jumpUp.assign(bbGatesList.size(), std::vector<size_t>(sizeLog + 1));
518 {
519 size_t timestamp = 0;
520 struct DFSState {
521 size_t cur;
522 std::vector<size_t> &succList;
523 size_t idx;
524 };
525 std::stack<DFSState> dfsStack;
526 size_t root = 0;
527 dfsStack.push({root, sonList[root], 0});
528 timeIn[root] = timestamp++;
529 jumpUp[root][0] = root;
530 for (size_t stepSize = 1; stepSize <= sizeLog; stepSize++) {
531 auto jumpUpHalf = jumpUp[root][stepSize - 1];
532 jumpUp[root][stepSize] = jumpUp[jumpUpHalf][stepSize - 1];
533 }
534 while (!dfsStack.empty()) {
535 auto &curState = dfsStack.top();
536 auto &cur = curState.cur;
537 auto &succList = curState.succList;
538 auto &idx = curState.idx;
539 if (idx == succList.size()) {
540 timeOut[cur] = timestamp++;
541 dfsStack.pop();
542 continue;
543 }
544 const auto &succ = succList[idx];
545 dfsStack.push({succ, sonList[succ], 0});
546 timeIn[succ] = timestamp++;
547 jumpUp[succ][0] = cur;
548 for (size_t stepSize = 1; stepSize <= sizeLog; stepSize++) {
549 auto jumpUpHalf = jumpUp[succ][stepSize - 1];
550 jumpUp[succ][stepSize] = jumpUp[jumpUpHalf][stepSize - 1];
551 }
552 idx++;
553 }
554 }
555 auto isAncestor = [timeIn, timeOut](size_t nodeA, size_t nodeB) -> bool {
556 return timeIn[nodeA] <= timeIn[nodeB] && timeOut[nodeA] >= timeOut[nodeB];
557 };
558 auto lowestCommonAncestor = [&](size_t nodeA, size_t nodeB) -> size_t {
559 if (isAncestor(nodeA, nodeB)) {
560 return nodeA;
561 }
562 if (isAncestor(nodeB, nodeA)) {
563 return nodeB;
564 }
565 for (size_t stepSize = sizeLog + 1; stepSize > 0; stepSize--) {
566 if (!isAncestor(jumpUp[nodeA][stepSize - 1], nodeB)) {
567 nodeA = jumpUp[nodeA][stepSize - 1];
568 }
569 }
570 return jumpUp[nodeA][0];
571 };
572 if (!RunCFGReducibilityCheck(circuit, bbGatesList, bbGatesAddrToIdx, isAncestor)) {
573 if (enableLog) {
574 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunCFGReducibilityCheck failed";
575 }
576 return false;
577 }
578 std::vector<GateRef> fixedGatesList;
579 FindFixedGates(circuit, bbGatesList, fixedGatesList);
580 if (!RunFixedGatesCheck(circuit, fixedGatesList)) {
581 if (enableLog) {
582 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunFixedGatesCheck failed";
583 }
584 return false;
585 }
586 if (!RunFixedGatesRelationsCheck(circuit, fixedGatesList, bbGatesAddrToIdx, isAncestor)) {
587 if (enableLog) {
588 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunFixedGatesRelationsCheck failed";
589 }
590 return false;
591 }
592 std::vector<GateRef> schedulableGatesList;
593 if (!RunFlowCyclesFind(circuit, &schedulableGatesList, bbGatesList, fixedGatesList)) {
594 if (enableLog) {
595 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunFlowCyclesFind failed";
596 }
597 return false;
598 }
599 if (!RunSchedulableGatesCheck(circuit, fixedGatesList)) {
600 if (enableLog) {
601 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunSchedulableGatesCheck failed";
602 }
603 return false;
604 }
605 if (!RunPrologGatesCheck(circuit, fixedGatesList)) {
606 if (enableLog) {
607 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunPrologGatesCheck failed";
608 }
609 return false;
610 }
611 if (!RunSchedulingBoundsCheck(circuit, schedulableGatesList, bbGatesAddrToIdx, isAncestor, lowestCommonAncestor)) {
612 if (enableLog) {
613 LOG_COMPILER(ERROR) << "[Verifier][Fail] RunSchedulingBoundsCheck failed";
614 }
615 return false;
616 }
617
618 if (enableLog) {
619 LOG_COMPILER(INFO) << "[Verifier][Pass] Verifier success";
620 }
621
622 return true;
623 }
624 } // namespace panda::ecmascript::kungfu
625