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 30namespace panda::ecmascript::kungfu { 31bool 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 112bool 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 121bool 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 143bool 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 191bool 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 220bool 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 228bool 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 265bool 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 361bool 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 369bool 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 384bool 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 420void 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 433bool 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 479bool 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