1 /*
2 * Copyright (c) 2023 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 "me_cfg.h"
17 #include <iostream>
18 #include <algorithm>
19 #include <string>
20 #include "bb.h"
21 #include "ssa_mir_nodes.h"
22 #include "me_irmap.h"
23 #include "mir_builder.h"
24 #include "mir_lower.h"
25 #include "maple_phase_manager.h"
26
27 namespace {
28 constexpr int kFuncNameLenLimit = 80;
29 }
30
31 namespace maple {
32 #define MATCH_STMT(stmt, kOpCode) \
33 do { \
34 while ((stmt) != nullptr && (stmt)->GetOpCode() == OP_comment) { \
35 (stmt) = (stmt)->GetNext(); \
36 } \
37 if ((stmt) == nullptr || (stmt)->GetOpCode() != (kOpCode)) { \
38 return false; \
39 } \
40 } while (0) // END define
41 // determine if need to be replaced by assertnonnull
IfReplaceWithAssertNonNull(const BB & bb) const42 bool MeCFG::IfReplaceWithAssertNonNull(const BB &bb) const
43 {
44 const StmtNode *stmt = bb.GetStmtNodes().begin().d();
45 constexpr const char npeTypeName[] = "Ljava_2Flang_2FNullPointerException_3B";
46 GStrIdx npeGStrIdx = GlobalTables::GetStrTable().GetStrIdxFromName(npeTypeName);
47 TyIdx npeTypeIdx = func.GetMIRModule().GetTypeNameTab()->GetTyIdxFromGStrIdx(npeGStrIdx);
48 // match first stmt
49 MATCH_STMT(stmt, OP_intrinsiccallwithtype);
50
51 auto *cNode = static_cast<const IntrinsiccallNode *>(stmt);
52 if (cNode->GetTyIdx() != npeTypeIdx) {
53 return false;
54 }
55 stmt = stmt->GetNext();
56 // match second stmt
57 MATCH_STMT(stmt, OP_dassign);
58
59 auto *dassignNode = static_cast<const DassignNode *>(stmt);
60 if (dassignNode->GetRHS()->GetOpCode() != OP_gcmalloc) {
61 return false;
62 }
63 auto *gcMallocNode = static_cast<GCMallocNode *>(dassignNode->GetRHS());
64 if (gcMallocNode->GetTyIdx() != npeTypeIdx) {
65 return false;
66 }
67 stmt = stmt->GetNext();
68 // match third stmt
69 MATCH_STMT(stmt, OP_callassigned);
70
71 auto *callNode = static_cast<const CallNode *>(stmt);
72 if (GlobalTables::GetFunctionTable().GetFunctionFromPuidx(callNode->GetPUIdx())->GetName() !=
73 "Ljava_2Flang_2FNullPointerException_3B_7C_3Cinit_3E_7C_28_29V") {
74 return false;
75 }
76 stmt = stmt->GetNext();
77 MATCH_STMT(stmt, OP_throw);
78
79 return true;
80 }
81
FindExprUse(const BaseNode & expr,StIdx stIdx) const82 bool MeCFG::FindExprUse(const BaseNode &expr, StIdx stIdx) const
83 {
84 if (expr.GetOpCode() == OP_addrof || expr.GetOpCode() == OP_dread) {
85 const auto &addofNode = static_cast<const AddrofNode &>(expr);
86 return addofNode.GetStIdx() == stIdx;
87 } else if (expr.GetOpCode() == OP_iread) {
88 return FindExprUse(*expr.Opnd(0), stIdx);
89 } else {
90 for (size_t i = 0; i < expr.NumOpnds(); ++i) {
91 if (FindExprUse(*expr.Opnd(i), stIdx)) {
92 return true;
93 }
94 }
95 }
96 return false;
97 }
98
FindUse(const StmtNode & stmt,StIdx stIdx) const99 bool MeCFG::FindUse(const StmtNode &stmt, StIdx stIdx) const
100 {
101 Opcode opcode = stmt.GetOpCode();
102 switch (opcode) {
103 case OP_call:
104 case OP_virtualcall:
105 case OP_virtualicall:
106 case OP_superclasscall:
107 case OP_interfacecall:
108 case OP_interfaceicall:
109 case OP_customcall:
110 case OP_polymorphiccall:
111 case OP_icall:
112 case OP_icallproto:
113 case OP_intrinsiccall:
114 case OP_xintrinsiccall:
115 case OP_intrinsiccallwithtype:
116 case OP_callassigned:
117 case OP_virtualcallassigned:
118 case OP_virtualicallassigned:
119 case OP_superclasscallassigned:
120 case OP_interfacecallassigned:
121 case OP_interfaceicallassigned:
122 case OP_customcallassigned:
123 case OP_polymorphiccallassigned:
124 case OP_icallassigned:
125 case OP_icallprotoassigned:
126 case OP_intrinsiccallassigned:
127 case OP_xintrinsiccallassigned:
128 case OP_intrinsiccallwithtypeassigned:
129 case OP_asm:
130 case OP_syncenter:
131 case OP_syncexit: {
132 for (size_t i = 0; i < stmt.NumOpnds(); ++i) {
133 BaseNode *argExpr = stmt.Opnd(i);
134 if (FindExprUse(*argExpr, stIdx)) {
135 return true;
136 }
137 }
138 break;
139 }
140 case OP_dassign: {
141 const auto &dNode = static_cast<const DassignNode &>(stmt);
142 return FindExprUse(*dNode.GetRHS(), stIdx);
143 }
144 case OP_regassign: {
145 const auto &rNode = static_cast<const RegassignNode &>(stmt);
146 if (rNode.GetRegIdx() < 0) {
147 return false;
148 }
149 return FindExprUse(*rNode.Opnd(0), stIdx);
150 }
151 case OP_iassign: {
152 const auto &iNode = static_cast<const IassignNode &>(stmt);
153 if (FindExprUse(*iNode.Opnd(0), stIdx)) {
154 return true;
155 } else {
156 return FindExprUse(*iNode.GetRHS(), stIdx);
157 }
158 }
159 CASE_OP_ASSERT_NONNULL
160 case OP_eval:
161 case OP_free:
162 case OP_switch: {
163 BaseNode *argExpr = stmt.Opnd(0);
164 return FindExprUse(*argExpr, stIdx);
165 }
166 default:
167 break;
168 }
169 return false;
170 }
171
FindDef(const StmtNode & stmt,StIdx stIdx) const172 bool MeCFG::FindDef(const StmtNode &stmt, StIdx stIdx) const
173 {
174 if (stmt.GetOpCode() != OP_dassign && !kOpcodeInfo.IsCallAssigned(stmt.GetOpCode())) {
175 return false;
176 }
177 if (stmt.GetOpCode() == OP_dassign) {
178 const auto &dassStmt = static_cast<const DassignNode &>(stmt);
179 return dassStmt.GetStIdx() == stIdx;
180 }
181 const auto &cNode = static_cast<const CallNode &>(stmt);
182 const CallReturnVector &nRets = cNode.GetReturnVec();
183 if (!nRets.empty()) {
184 DEBUG_ASSERT(nRets.size() == 1, "Single Ret value for now.");
185 StIdx idx = nRets[0].first;
186 RegFieldPair regFieldPair = nRets[0].second;
187 if (!regFieldPair.IsReg()) {
188 return idx == stIdx;
189 }
190 }
191 return false;
192 }
193
194 // Return true if there is no use or def of sym betweent from to to.
HasNoOccBetween(StmtNode & from,const StmtNode & to,StIdx stIdx) const195 bool MeCFG::HasNoOccBetween(StmtNode &from, const StmtNode &to, StIdx stIdx) const
196 {
197 for (StmtNode *stmt = &from; stmt && stmt != &to; stmt = stmt->GetNext()) {
198 if (FindUse(*stmt, stIdx) || FindDef(*stmt, stIdx)) {
199 return false;
200 }
201 }
202 return true;
203 }
204
IsStartTryBB(maple::BB & meBB) const205 bool MeCFG::IsStartTryBB(maple::BB &meBB) const
206 {
207 if (!meBB.GetAttributes(kBBAttrIsTry) || meBB.GetAttributes(kBBAttrIsTryEnd)) {
208 return false;
209 }
210 return (!meBB.GetStmtNodes().empty() && meBB.GetStmtNodes().front().GetOpCode() == OP_try);
211 }
212
213 // CFG Verify
214 // Check bb-vec and bb-list are strictly consistent.
Verify() const215 void MeCFG::Verify() const
216 {
217 // Check every bb in bb-list.
218 auto eIt = valid_end();
219 for (auto bIt = valid_begin(); bIt != eIt; ++bIt) {
220 if (bIt == common_entry() || bIt == common_exit()) {
221 continue;
222 }
223 auto *bb = *bIt;
224 DEBUG_ASSERT(bb->GetBBId() < bbVec.size(), "CFG Error!");
225 DEBUG_ASSERT(bbVec.at(bb->GetBBId()) == bb, "CFG Error!");
226 if (bb->IsEmpty()) {
227 continue;
228 }
229 DEBUG_ASSERT(bb->GetKind() != kBBUnknown, "runtime check error");
230 // verify succ[1] is goto bb
231 if (bb->GetKind() == kBBCondGoto) {
232 if (!bb->GetAttributes(kBBAttrIsTry) && !bb->GetAttributes(kBBAttrWontExit)) {
233 DEBUG_ASSERT(bb->GetStmtNodes().rbegin().base().d() != nullptr, "runtime check error");
234 DEBUG_ASSERT(bb->GetSucc().size() == kBBVectorInitialSize, "runtime check error");
235 }
236 DEBUG_ASSERT(bb->GetSucc(1)->GetBBLabel() ==
237 static_cast<CondGotoNode &>(bb->GetStmtNodes().back()).GetOffset(),
238 "runtime check error");
239 } else if (bb->GetKind() == kBBGoto) {
240 if (bb->GetStmtNodes().back().GetOpCode() == OP_throw) {
241 continue;
242 }
243 if (!bb->GetAttributes(kBBAttrIsTry) && !bb->GetAttributes(kBBAttrWontExit)) {
244 DEBUG_ASSERT(bb->GetStmtNodes().rbegin().base().d() != nullptr, "runtime check error");
245 DEBUG_ASSERT(bb->GetSucc().size() == 1, "runtime check error");
246 }
247 DEBUG_ASSERT(bb->GetSucc(0)->GetBBLabel() == static_cast<GotoNode &>(bb->GetStmtNodes().back()).GetOffset(),
248 "runtime check error");
249 }
250 }
251 }
252
253 // check that all the target labels in jump statements are defined
VerifyLabels() const254 void MeCFG::VerifyLabels() const
255 {
256 auto eIt = valid_end();
257 for (auto bIt = valid_begin(); bIt != eIt; ++bIt) {
258 BB *mirBB = *bIt;
259 auto &stmtNodes = mirBB->GetStmtNodes();
260 if (stmtNodes.rbegin().base().d() == nullptr) {
261 continue;
262 }
263 if (mirBB->GetKind() == kBBGoto) {
264 if (stmtNodes.back().GetOpCode() == OP_throw) {
265 continue;
266 }
267 DEBUG_ASSERT(GetLabelBBAt(static_cast<GotoNode &>(stmtNodes.back()).GetOffset())->GetBBLabel() ==
268 static_cast<GotoNode &>(stmtNodes.back()).GetOffset(),
269 "undefined label in goto");
270 } else if (mirBB->GetKind() == kBBCondGoto) {
271 DEBUG_ASSERT(GetLabelBBAt(static_cast<CondGotoNode &>(stmtNodes.back()).GetOffset())->GetBBLabel() ==
272 static_cast<CondGotoNode &>(stmtNodes.back()).GetOffset(),
273 "undefined label in conditional branch");
274 } else if (mirBB->GetKind() == kBBSwitch) {
275 auto &switchStmt = static_cast<SwitchNode &>(stmtNodes.back());
276 LabelIdx targetLabIdx = switchStmt.GetDefaultLabel();
277 [[maybe_unused]] BB *bb = GetLabelBBAt(targetLabIdx);
278 DEBUG_ASSERT(bb->GetBBLabel() == targetLabIdx, "undefined label in switch");
279 for (size_t j = 0; j < switchStmt.GetSwitchTable().size(); ++j) {
280 targetLabIdx = switchStmt.GetCasePair(j).second;
281 bb = GetLabelBBAt(targetLabIdx);
282 DEBUG_ASSERT(bb->GetBBLabel() == targetLabIdx, "undefined switch target label");
283 }
284 }
285 }
286 }
287
Dump() const288 void MeCFG::Dump() const
289 {
290 // BSF Dump the cfg
291 LogInfo::MapleLogger() << "####### CFG Dump: ";
292 DEBUG_ASSERT(NumBBs() != 0, "size to be allocated is 0");
293 auto *visitedMap = static_cast<bool *>(calloc(NumBBs(), sizeof(bool)));
294 if (visitedMap != nullptr) {
295 std::queue<BB *> qu;
296 qu.push(GetFirstBB());
297 while (!qu.empty()) {
298 BB *bb = qu.front();
299 qu.pop();
300 if (bb == nullptr) {
301 continue;
302 }
303 BBId id = bb->GetBBId();
304 if (visitedMap[static_cast<long>(id)]) {
305 continue;
306 }
307 LogInfo::MapleLogger() << id << " ";
308 visitedMap[static_cast<long>(id)] = true;
309 auto it = bb->GetSucc().begin();
310 while (it != bb->GetSucc().end()) {
311 BB *kidBB = *it;
312 if (!visitedMap[static_cast<long>(kidBB->GetBBId())]) {
313 qu.push(kidBB);
314 }
315 ++it;
316 }
317 }
318 LogInfo::MapleLogger() << '\n';
319 free(visitedMap);
320 }
321 }
322
323 // replace special char in FunctionName for output file
ReplaceFilename(std::string & fileName)324 static void ReplaceFilename(std::string &fileName)
325 {
326 for (char &c : fileName) {
327 if (c == ';' || c == '/' || c == '|') {
328 c = '_';
329 }
330 }
331 }
332
ConstructFileNameToDump(const std::string & prefix) const333 std::string MeCFG::ConstructFileNameToDump(const std::string &prefix) const
334 {
335 std::string fileName;
336 if (!prefix.empty()) {
337 fileName.append(prefix);
338 fileName.append("-");
339 }
340 // the func name length may exceed OS's file name limit, so truncate after 80 chars
341 if (func.GetName().size() <= kFuncNameLenLimit) {
342 fileName.append(func.GetName());
343 } else {
344 fileName.append(func.GetName().c_str(), kFuncNameLenLimit);
345 }
346 ReplaceFilename(fileName);
347 fileName.append(".dot");
348 return fileName;
349 }
350
NewBasicBlock()351 BB *MeCFG::NewBasicBlock()
352 {
353 BB *newBB = memPool->New<BB>(&mecfgAlloc, &func.GetVersAlloc(), BBId(nextBBId++));
354 bbVec.push_back(newBB);
355 return newBB;
356 }
357
358 // new a basic block and insert before position or after position
InsertNewBasicBlock(const BB & position,bool isInsertBefore)359 BB &MeCFG::InsertNewBasicBlock(const BB &position, bool isInsertBefore)
360 {
361 BB *newBB = memPool->New<BB>(&mecfgAlloc, &func.GetVersAlloc(), BBId(nextBBId++));
362
363 auto bIt = std::find(begin(), end(), &position);
364 auto idx = position.GetBBId();
365 if (!isInsertBefore) {
366 ++bIt;
367 ++idx;
368 }
369 auto newIt = bbVec.insert(bIt, newBB);
370 auto eIt = end();
371 // update bb's idx
372 for (auto it = newIt; it != eIt; ++it) {
373 if ((*it) != nullptr) {
374 (*it)->SetBBId(BBId(idx));
375 }
376 ++idx;
377 }
378 return *newBB;
379 }
380
DeleteBasicBlock(const BB & bb)381 void MeCFG::DeleteBasicBlock(const BB &bb)
382 {
383 DEBUG_ASSERT(bbVec[bb.GetBBId()] == &bb, "runtime check error");
384 /* update first_bb_ and last_bb if needed */
385 bbVec.at(bb.GetBBId()) = nullptr;
386 }
387
388 /* get next bb in bbVec */
NextBB(const BB * bb)389 BB *MeCFG::NextBB(const BB *bb)
390 {
391 auto bbIt = std::find(begin(), end(), bb);
392 CHECK_FATAL(bbIt != end(), "bb must be inside bb_vec");
393 for (auto it = ++bbIt; it != end(); ++it) {
394 if (*it != nullptr) {
395 return *it;
396 }
397 }
398 return nullptr;
399 }
400
401 /* get prev bb in bbVec */
PrevBB(const BB * bb)402 BB *MeCFG::PrevBB(const BB *bb)
403 {
404 auto bbIt = std::find(rbegin(), rend(), bb);
405 CHECK_FATAL(bbIt != rend(), "bb must be inside bb_vec");
406 for (auto it = ++bbIt; it != rend(); ++it) {
407 if (*it != nullptr) {
408 return *it;
409 }
410 }
411 return nullptr;
412 }
413
SetTryBlockInfo(const StmtNode * nextStmt,StmtNode * tryStmt,BB * lastTryBB,BB * curBB,BB * newBB)414 void MeCFG::SetTryBlockInfo(const StmtNode *nextStmt, StmtNode *tryStmt, BB *lastTryBB, BB *curBB, BB *newBB)
415 {
416 if (nextStmt->GetOpCode() == OP_endtry) {
417 curBB->SetAttributes(kBBAttrIsTryEnd);
418 DEBUG_ASSERT(lastTryBB != nullptr, "null ptr check");
419 endTryBB2TryBB[curBB] = lastTryBB;
420 } else {
421 newBB->SetAttributes(kBBAttrIsTry);
422 bbTryNodeMap[newBB] = tryStmt;
423 }
424 }
425
CreateBasicBlocks()426 void MeCFG::CreateBasicBlocks()
427 {
428 if (func.CurFunction()->IsEmpty()) {
429 if (!MeOption::quiet) {
430 LogInfo::MapleLogger() << "function is empty, cfg is nullptr\n";
431 }
432 return;
433 }
434 // create common_entry/exit bb first as bbVec[0] and bb_vec[1]
435 bool isJavaModule = func.GetMIRModule().IsJavaModule();
436 auto *commonEntryBB = NewBasicBlock();
437 commonEntryBB->SetAttributes(kBBAttrIsEntry);
438 auto *commonExitBB = NewBasicBlock();
439 commonExitBB->SetAttributes(kBBAttrIsExit);
440 auto *firstBB = NewBasicBlock();
441 firstBB->SetAttributes(kBBAttrIsEntry);
442 StmtNode *nextStmt = func.CurFunction()->GetBody()->GetFirst();
443 DEBUG_ASSERT(nextStmt != nullptr, "function has no statement");
444 BB *curBB = firstBB;
445 StmtNode *tryStmt = nullptr; // record current try stmt for map<bb, try_stmt>
446 BB *lastTryBB = nullptr; // bb containing try_stmt
447 do {
448 StmtNode *stmt = nextStmt;
449 nextStmt = stmt->GetNext();
450 switch (stmt->GetOpCode()) {
451 case OP_goto: {
452 if (curBB->IsEmpty()) {
453 curBB->SetFirst(stmt);
454 }
455 curBB->SetLast(stmt);
456 curBB->SetKind(kBBGoto);
457 if (nextStmt != nullptr) {
458 BB *newBB = NewBasicBlock();
459 if (tryStmt != nullptr) {
460 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
461 }
462 curBB = newBB;
463 }
464 break;
465 }
466 case OP_igoto: {
467 if (curBB->IsEmpty()) {
468 curBB->SetFirst(stmt);
469 }
470 curBB->SetLast(stmt);
471 curBB->SetKind(kBBIgoto);
472 if (nextStmt != nullptr) {
473 curBB = NewBasicBlock();
474 }
475 break;
476 }
477 case OP_dassign: {
478 DassignNode *dass = static_cast<DassignNode *>(stmt);
479 // delete identity assignments inserted by LFO
480 if (dass->GetRHS()->GetOpCode() == OP_dread) {
481 DreadNode *dread = static_cast<DreadNode *>(dass->GetRHS());
482 if (dass->GetStIdx() == dread->GetStIdx() && dass->GetFieldID() == dread->GetFieldID()) {
483 func.CurFunction()->GetBody()->RemoveStmt(stmt);
484 break;
485 }
486 }
487 if (curBB->IsEmpty()) {
488 curBB->SetFirst(stmt);
489 }
490 if (isJavaModule && dass->GetRHS()->MayThrowException()) {
491 stmt->SetOpCode(OP_maydassign);
492 if (tryStmt != nullptr) {
493 // breaks new BB only inside try blocks
494 curBB->SetLast(stmt);
495 curBB->SetKind(kBBFallthru);
496 BB *newBB = NewBasicBlock();
497 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
498 curBB = newBB;
499 break;
500 }
501 }
502 if ((nextStmt == nullptr) && to_ptr(curBB->GetStmtNodes().rbegin()) == nullptr) {
503 curBB->SetLast(stmt);
504 }
505 break;
506 }
507 case OP_brfalse:
508 case OP_brtrue: {
509 if (curBB->IsEmpty()) {
510 curBB->SetFirst(stmt);
511 }
512 curBB->SetLast(stmt);
513 curBB->SetKind(kBBCondGoto);
514 BB *newBB = NewBasicBlock();
515 if (tryStmt != nullptr) {
516 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
517 }
518 curBB = newBB;
519 break;
520 }
521 case OP_if:
522 case OP_doloop:
523 case OP_dowhile:
524 case OP_while: {
525 DEBUG_ASSERT(false, "not yet implemented");
526 break;
527 }
528 case OP_throw:
529 if (tryStmt != nullptr) {
530 // handle as goto
531 if (curBB->IsEmpty()) {
532 curBB->SetFirst(stmt);
533 }
534 curBB->SetLast(stmt);
535 curBB->SetKind(kBBGoto);
536 if (nextStmt != nullptr) {
537 BB *newBB = NewBasicBlock();
538 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
539 curBB = newBB;
540 }
541 break;
542 }
543 // fall thru to handle as return
544 [[clang::fallthrough]];
545 case OP_gosub:
546 case OP_retsub:
547 case OP_return: {
548 if (curBB->IsEmpty()) {
549 curBB->SetFirst(stmt);
550 }
551 curBB->SetLast(stmt);
552 curBB->SetKindReturn();
553 if (nextStmt != nullptr) {
554 BB *newBB = NewBasicBlock();
555 if (tryStmt != nullptr) {
556 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
557 }
558 curBB = newBB;
559 if (stmt->GetOpCode() == OP_gosub) {
560 curBB->SetAttributes(kBBAttrIsEntry);
561 }
562 }
563 break;
564 }
565 case OP_endtry:
566 if (isJavaModule) {
567 if (tryStmt == nullptr) {
568 break;
569 }
570 /* skip OP_entry and generate it in emit phase */
571 DEBUG_ASSERT(lastTryBB != nullptr, "null ptr check");
572 tryStmt = nullptr; // reset intryblocks
573 if (!curBB->IsEmpty()) {
574 StmtNode *lastStmt = stmt->GetPrev();
575 DEBUG_ASSERT(curBB->GetStmtNodes().rbegin().base().d() == nullptr ||
576 curBB->GetStmtNodes().rbegin().base().d() == lastStmt,
577 "something wrong building BB");
578 curBB->SetLast(lastStmt);
579 if (curBB->GetKind() == kBBUnknown) {
580 curBB->SetKind(kBBFallthru);
581 }
582 curBB->SetAttributes(kBBAttrIsTryEnd);
583 SetBBTryBBMap(curBB, lastTryBB);
584 curBB = NewBasicBlock();
585 } else if (curBB->GetBBLabel() != 0) {
586 // create the empty BB
587 curBB->SetKind(kBBFallthru);
588 curBB->SetAttributes(kBBAttrIsTryEnd);
589 SetBBTryBBMap(curBB, lastTryBB);
590 curBB = NewBasicBlock();
591 } else {
592 } // endtry has already been processed in SetTryBlockInfo()
593 lastTryBB = nullptr;
594 } else {
595 if (curBB->IsEmpty()) {
596 curBB->SetFirst(stmt);
597 }
598 if ((nextStmt == nullptr) && (curBB->GetStmtNodes().rbegin().base().d() == nullptr)) {
599 curBB->SetLast(stmt);
600 }
601 }
602 break;
603 case OP_try: {
604 // start a new bb or with a label
605 if (!curBB->IsEmpty()) {
606 // prepare a new bb
607 StmtNode *lastStmt = stmt->GetPrev();
608 DEBUG_ASSERT(curBB->GetStmtNodes().rbegin().base().d() == nullptr ||
609 curBB->GetStmtNodes().rbegin().base().d() == lastStmt,
610 "something wrong building BB");
611 curBB->SetLast(lastStmt);
612 if (curBB->GetKind() == kBBUnknown) {
613 curBB->SetKind(kBBFallthru);
614 }
615 BB *newBB = NewBasicBlock();
616 // assume no nested try, so no need to call SetTryBlockInfo()
617 curBB = newBB;
618 }
619 curBB->SetFirst(stmt);
620 tryStmt = stmt;
621 lastTryBB = curBB;
622 curBB->SetAttributes(kBBAttrIsTry);
623 bbTryNodeMap[curBB] = tryStmt;
624 // prepare a new bb that contains only a OP_try. It is needed for
625 // dse to work correctly: assignments in a try block should not affect
626 // assignments before the try block as exceptions might occur.
627 curBB->SetLast(stmt);
628 curBB->SetKind(kBBFallthru);
629 BB *newBB = NewBasicBlock();
630 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
631 curBB = newBB;
632 break;
633 }
634 case OP_catch: {
635 // start a new bb or with a label
636 if (!curBB->IsEmpty()) {
637 // prepare a new bb
638 StmtNode *lastStmt = stmt->GetPrev();
639 DEBUG_ASSERT(curBB->GetStmtNodes().rbegin().base().d() == nullptr ||
640 curBB->GetStmtNodes().rbegin().base().d() == lastStmt,
641 "something wrong building BB");
642 curBB->SetLast(lastStmt);
643 if (curBB->GetKind() == kBBUnknown) {
644 curBB->SetKind(kBBFallthru);
645 }
646 BB *newBB = NewBasicBlock();
647 if (tryStmt != nullptr) {
648 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
649 }
650 curBB = newBB;
651 }
652 curBB->SetFirst(stmt);
653 curBB->SetAttributes(kBBAttrIsCatch);
654 auto *catchNode = static_cast<CatchNode *>(stmt);
655 const MapleVector<TyIdx> &exceptionTyIdxVec = catchNode->GetExceptionTyIdxVec();
656
657 for (TyIdx exceptIdx : exceptionTyIdxVec) {
658 MIRType *eType = GlobalTables::GetTypeTable().GetTypeFromTyIdx(exceptIdx);
659 DEBUG_ASSERT(eType != nullptr &&
660 (eType->GetPrimType() == PTY_ptr || eType->GetPrimType() == PTY_ref),
661 "wrong exception type");
662 auto *exceptType = static_cast<MIRPtrType *>(eType);
663 MIRType *pointType = GlobalTables::GetTypeTable().GetTypeFromTyIdx(exceptType->GetPointedTyIdx());
664 const std::string &eName =
665 GlobalTables::GetStrTable().GetStringFromStrIdx(pointType->GetNameStrIdx());
666 if ((pointType->GetPrimType() == PTY_void) || (eName == "Ljava/lang/Throwable;") ||
667 (eName == "Ljava/lang/Exception;")) {
668 // "Ljava/lang/Exception;" is risk to set isJavaFinally because it
669 // only deal with "throw exception". if throw error, it's wrong
670 curBB->SetAttributes(kBBAttrIsJavaFinally); // this is a start of finally handler
671 }
672 }
673 break;
674 }
675 case OP_label: {
676 auto *labelNode = static_cast<LabelNode *>(stmt);
677 LabelIdx labelIdx = labelNode->GetLabelIdx();
678 if (func.IsPme() && curBB == firstBB && curBB->IsEmpty()) {
679 // when function starts with a label, need to insert dummy BB as entry
680 curBB = NewBasicBlock();
681 }
682 if (!curBB->IsEmpty() || curBB->GetBBLabel() != 0) {
683 // prepare a new bb
684 StmtNode *lastStmt = stmt->GetPrev();
685 DEBUG_ASSERT((curBB->GetStmtNodes().rbegin().base().d() == nullptr ||
686 curBB->GetStmtNodes().rbegin().base().d() == lastStmt),
687 "something wrong building BB");
688 if (curBB->GetStmtNodes().rbegin().base().d() == nullptr && (lastStmt->GetOpCode() != OP_label)) {
689 if (isJavaModule && lastStmt->GetOpCode() == OP_endtry) {
690 if (curBB->GetStmtNodes().empty()) {
691 curBB->SetLast(nullptr);
692 } else {
693 // find a valid stmt which is not label or endtry
694 StmtNode *p = lastStmt->GetPrev();
695 DEBUG_ASSERT(p != nullptr, "null ptr check");
696 DEBUG_ASSERT(p->GetOpCode() != OP_label, "runtime check error");
697 DEBUG_ASSERT(p->GetOpCode() != OP_endtry, "runtime check error");
698 curBB->SetLast(p);
699 }
700 } else {
701 curBB->SetLast(lastStmt);
702 }
703 }
704 if (curBB->GetKind() == kBBUnknown) {
705 curBB->SetKind(kBBFallthru);
706 }
707 BB *newBB = NewBasicBlock();
708 if (tryStmt != nullptr) {
709 newBB->SetAttributes(kBBAttrIsTry);
710 SetBBTryNodeMap(*newBB, *tryStmt);
711 }
712 curBB = newBB;
713 } else if (func.GetPreMeFunc() && (func.GetPreMeFunc()->label2WhileInfo.find(labelIdx) !=
714 func.GetPreMeFunc()->label2WhileInfo.end())) {
715 curBB->SetKind(kBBFallthru);
716 BB *newBB = NewBasicBlock();
717 if (tryStmt != nullptr) {
718 newBB->SetAttributes(kBBAttrIsTry);
719 SetBBTryNodeMap(*newBB, *tryStmt);
720 }
721 curBB = newBB;
722 }
723 labelBBIdMap[labelIdx] = curBB;
724 curBB->SetBBLabel(labelIdx);
725 // label node is not real node in bb, get frequency information to bb
726 if (Options::profileUse && func.GetMirFunc()->GetFuncProfData()) {
727 auto freq = func.GetMirFunc()->GetFuncProfData()->GetStmtFreq(stmt->GetStmtID());
728 if (freq >= 0) {
729 curBB->SetFrequency(freq);
730 }
731 }
732 break;
733 }
734 case OP_jscatch: {
735 if (curBB->IsEmpty()) {
736 curBB->SetFirst(stmt);
737 }
738 curBB->SetAttributes(kBBAttrIsEntry);
739 curBB->SetAttributes(kBBAttrIsJSCatch);
740 break;
741 }
742 case OP_finally: {
743 DEBUG_ASSERT(curBB->GetStmtNodes().empty(), "runtime check error");
744 curBB->SetFirst(stmt);
745 curBB->SetAttributes(kBBAttrIsEntry);
746 curBB->SetAttributes(kBBAttrIsJSFinally);
747 break;
748 }
749 case OP_switch: {
750 if (curBB->IsEmpty()) {
751 curBB->SetFirst(stmt);
752 }
753 curBB->SetLast(stmt);
754 curBB->SetKind(kBBSwitch);
755 BB *newBB = NewBasicBlock();
756 if (tryStmt != nullptr) {
757 SetTryBlockInfo(nextStmt, tryStmt, lastTryBB, curBB, newBB);
758 }
759 curBB = newBB;
760 break;
761 }
762 default: {
763 if (curBB->IsEmpty()) {
764 curBB->SetFirst(stmt);
765 }
766 if ((nextStmt == nullptr) && (curBB->GetStmtNodes().rbegin().base().d() == nullptr)) {
767 curBB->SetLast(stmt);
768 }
769 break;
770 }
771 }
772 } while (nextStmt != nullptr);
773 DEBUG_ASSERT(tryStmt == nullptr, "unclosed try"); // tryandendtry should be one-one mapping
774 DEBUG_ASSERT(lastTryBB == nullptr, "unclosed tryBB"); // tryandendtry should be one-one mapping
775 auto *lastBB = curBB;
776 if (lastBB->IsEmpty()) {
777 // insert a return statement
778 lastBB->SetFirst(func.GetMIRModule().GetMIRBuilder()->CreateStmtReturn(nullptr));
779 lastBB->SetLast(lastBB->GetStmtNodes().begin().d());
780 lastBB->SetKindReturn();
781 } else if (lastBB->GetKind() == kBBUnknown) {
782 lastBB->SetKindReturn();
783 lastBB->SetAttributes(kBBAttrIsExit);
784 }
785 }
786
BuildSCCDFS(BB & bb,uint32 & visitIndex,std::vector<SCCOfBBs * > & sccNodes,std::vector<uint32> & visitedOrder,std::vector<uint32> & lowestOrder,std::vector<bool> & inStack,std::stack<uint32> & visitStack)787 void MeCFG::BuildSCCDFS(BB &bb, uint32 &visitIndex, std::vector<SCCOfBBs *> &sccNodes,
788 std::vector<uint32> &visitedOrder, std::vector<uint32> &lowestOrder, std::vector<bool> &inStack,
789 std::stack<uint32> &visitStack)
790 {
791 uint32 id = bb.UintID();
792 visitedOrder[id] = visitIndex;
793 lowestOrder[id] = visitIndex;
794 ++visitIndex;
795 visitStack.push(id);
796 inStack[id] = true;
797
798 for (BB *succ : bb.GetSucc()) {
799 if (succ == nullptr) {
800 continue;
801 }
802 uint32 succId = succ->UintID();
803 if (!visitedOrder[succId]) {
804 BuildSCCDFS(*succ, visitIndex, sccNodes, visitedOrder, lowestOrder, inStack, visitStack);
805 if (lowestOrder[succId] < lowestOrder[id]) {
806 lowestOrder[id] = lowestOrder[succId];
807 }
808 } else if (inStack[succId]) {
809 (void)backEdges.emplace(std::pair<uint32, uint32>(id, succId));
810 if (visitedOrder[succId] < lowestOrder[id]) {
811 lowestOrder[id] = visitedOrder[succId];
812 }
813 }
814 }
815
816 if (visitedOrder.at(id) == lowestOrder.at(id)) {
817 auto *sccNode = GetAlloc().GetMemPool()->New<SCCOfBBs>(numOfSCCs++, &bb, &GetAlloc());
818 uint32 stackTopId;
819 do {
820 stackTopId = visitStack.top();
821 visitStack.pop();
822 inStack[stackTopId] = false;
823 auto *topBB = static_cast<BB *>(GetAllBBs()[stackTopId]);
824 sccNode->AddBBNode(topBB);
825 sccOfBB[stackTopId] = sccNode;
826 } while (stackTopId != id);
827
828 sccNodes.push_back(sccNode);
829 }
830 }
831
VerifySCC()832 void MeCFG::VerifySCC()
833 {
834 for (BB *bb : GetAllBBs()) {
835 if (bb == nullptr || bb == GetCommonExitBB()) {
836 continue;
837 }
838 SCCOfBBs *scc = sccOfBB.at(bb->UintID());
839 CHECK_FATAL(scc != nullptr, "bb should belong to a scc");
840 }
841 }
842
SCCTopologicalSort(std::vector<SCCOfBBs * > & sccNodes)843 void MeCFG::SCCTopologicalSort(std::vector<SCCOfBBs *> &sccNodes)
844 {
845 std::set<SCCOfBBs *> inQueue;
846 for (SCCOfBBs *node : sccNodes) {
847 if (!node->HasPred()) {
848 sccTopologicalVec.push_back(node);
849 (void)inQueue.insert(node);
850 }
851 }
852
853 // Top-down iterates all nodes
854 for (size_t i = 0; i < sccTopologicalVec.size(); ++i) {
855 SCCOfBBs *sccBB = sccTopologicalVec[i];
856 for (SCCOfBBs *succ : sccBB->GetSucc()) {
857 if (inQueue.find(succ) == inQueue.end()) {
858 // successor has not been visited
859 bool predAllVisited = true;
860 // check whether all predecessors of the current successor have been visited
861 for (SCCOfBBs *pred : succ->GetPred()) {
862 if (inQueue.find(pred) == inQueue.end()) {
863 predAllVisited = false;
864 break;
865 }
866 }
867 if (predAllVisited) {
868 sccTopologicalVec.push_back(succ);
869 (void)inQueue.insert(succ);
870 }
871 }
872 }
873 }
874 }
875
876 // BBId is index of BB in the bbVec, so we should swap two BB's pos in bbVec, if we want to swap their BBId.
SwapBBId(BB & bb1,BB & bb2)877 void MeCFG::SwapBBId(BB &bb1, BB &bb2)
878 {
879 bbVec[bb1.GetBBId()] = &bb2;
880 bbVec[bb2.GetBBId()] = &bb1;
881 BBId tmp = bb1.GetBBId();
882 bb1.SetBBId(bb2.GetBBId());
883 bb2.SetBBId(tmp);
884 }
885
886 // set bb succ frequency from bb freq
887 // no critical edge is expected
ConstructEdgeFreqFromBBFreq()888 void MeCFG::ConstructEdgeFreqFromBBFreq()
889 {
890 // set succfreqs
891 auto eIt = valid_end();
892 for (auto bIt = valid_begin(); bIt != eIt; ++bIt) {
893 auto *bb = *bIt;
894 if (!bb)
895 continue;
896 if (bb->GetSucc().size() == 1) {
897 bb->PushBackSuccFreq(bb->GetFrequency());
898 } else if (bb->GetSucc().size() == 2) { // bb has 2 succeed
899 auto *fallthru = bb->GetSucc(0);
900 auto *targetBB = bb->GetSucc(1);
901 if (fallthru->GetPred().size() == 1) {
902 auto succ0Freq = fallthru->GetFrequency();
903 bb->PushBackSuccFreq(succ0Freq);
904 DEBUG_ASSERT(bb->GetFrequency() >= succ0Freq, "sanity check");
905 bb->PushBackSuccFreq(bb->GetFrequency() - succ0Freq);
906 } else if (targetBB->GetPred().size() == 1) {
907 auto succ1Freq = targetBB->GetFrequency();
908 DEBUG_ASSERT(bb->GetFrequency() >= succ1Freq, "sanity check");
909 bb->PushBackSuccFreq(bb->GetFrequency() - succ1Freq);
910 bb->PushBackSuccFreq(succ1Freq);
911 } else {
912 CHECK_FATAL(false, "ConstructEdgeFreqFromBBFreq::NYI critical edge");
913 }
914 } else if (bb->GetSucc().size() > 2) { // bb has 2 succeed
915 // switch case, no critical edge is supposted
916 for (size_t i = 0; i < bb->GetSucc().size(); ++i) {
917 bb->PushBackSuccFreq(bb->GetSucc(i)->GetFrequency());
918 }
919 }
920 }
921 }
922
923 // set bb frequency from stmt record
ConstructBBFreqFromStmtFreq()924 void MeCFG::ConstructBBFreqFromStmtFreq()
925 {
926 GcovFuncInfo *funcData = func.GetMirFunc()->GetFuncProfData();
927 if (!funcData)
928 return;
929 if (funcData->stmtFreqs.size() == 0)
930 return;
931 auto eIt = valid_end();
932 for (auto bIt = valid_begin(); bIt != eIt; ++bIt) {
933 if ((*bIt)->IsEmpty())
934 continue;
935 StmtNode &first = (*bIt)->GetFirst();
936 if (funcData->stmtFreqs.count(first.GetStmtID()) > 0) {
937 (*bIt)->SetFrequency(funcData->stmtFreqs[first.GetStmtID()]);
938 } else if (funcData->stmtFreqs.count((*bIt)->GetLast().GetStmtID()) > 0) {
939 (*bIt)->SetFrequency(funcData->stmtFreqs[(*bIt)->GetLast().GetStmtID()]);
940 } else {
941 LogInfo::MapleLogger() << "ERROR:: bb " << (*bIt)->GetBBId() << "frequency is not set"
942 << "\n";
943 DEBUG_ASSERT(0, "no freq set");
944 }
945 }
946 // add common entry and common exit
947 auto *bb = *common_entry();
948 uint64_t freq = 0;
949 for (size_t i = 0; i < bb->GetSucc().size(); ++i) {
950 freq += bb->GetSucc(i)->GetFrequency();
951 }
952 bb->SetFrequency(freq);
953 bb = *common_exit();
954 freq = 0;
955 for (size_t i = 0; i < bb->GetPred().size(); ++i) {
956 freq += bb->GetPred(i)->GetFrequency();
957 }
958 bb->SetFrequency(freq);
959 // set succfreqs
960 ConstructEdgeFreqFromBBFreq();
961 // clear stmtFreqs since cfg frequency is create
962 funcData->stmtFreqs.clear();
963 }
964
ConstructStmtFreq()965 void MeCFG::ConstructStmtFreq()
966 {
967 GcovFuncInfo *funcData = func.GetMirFunc()->GetFuncProfData();
968 if (!funcData)
969 return;
970 auto eIt = valid_end();
971 // clear stmtFreqs
972 funcData->stmtFreqs.clear();
973 for (auto bIt = valid_begin(); bIt != eIt; ++bIt) {
974 auto *bb = *bIt;
975 if (bIt == common_entry()) {
976 funcData->entry_freq = bb->GetFrequency();
977 funcData->real_entryfreq = funcData->entry_freq;
978 }
979 for (auto &stmt : bb->GetStmtNodes()) {
980 Opcode op = stmt.GetOpCode();
981 // record bb start/end stmt
982 if (stmt.GetStmtID() == bb->GetFirst().GetStmtID() || stmt.GetStmtID() == bb->GetLast().GetStmtID() ||
983 IsCallAssigned(op) || op == OP_call) {
984 funcData->stmtFreqs[stmt.GetStmtID()] = bb->GetFrequency();
985 }
986 }
987 }
988 }
989
VerifyBBFreq()990 void MeCFG::VerifyBBFreq()
991 {
992 for (size_t i = 2; i < bbVec.size(); ++i) { // skip common entry and common exit
993 auto *bb = bbVec[i];
994 if (bb == nullptr || bb->GetAttributes(kBBAttrIsEntry) || bb->GetAttributes(kBBAttrIsExit)) {
995 continue;
996 }
997 // wontexit bb may has wrong succ, skip it
998 if (bb->GetSuccFreq().size() != bb->GetSucc().size() && !bb->GetAttributes(kBBAttrWontExit)) {
999 CHECK_FATAL(false, "VerifyBBFreq: succFreq size != succ size");
1000 }
1001 // bb freq == sum(out edge freq)
1002 uint64 succSumFreq = 0;
1003 for (auto succFreq : bb->GetSuccFreq()) {
1004 succSumFreq += succFreq;
1005 }
1006 if (succSumFreq != bb->GetFrequency()) {
1007 LogInfo::MapleLogger() << "[VerifyFreq failure] BB" << bb->GetBBId() << " freq: " << bb->GetFrequency()
1008 << ", all succ edge freq sum: " << succSumFreq << std::endl;
1009 LogInfo::MapleLogger() << func.GetName() << std::endl;
1010 CHECK_FATAL(false, "VerifyFreq failure: bb freq != succ freq sum");
1011 }
1012 }
1013 }
1014 } // namespace maple
1015