| 358 | } |
| 359 | |
| 360 | void StackLayoutGenerator::processEntryPoint(CFG::BasicBlock const& _entry, CFG::FunctionInfo const* _functionInfo) |
| 361 | { |
| 362 | std::list<CFG::BasicBlock const*> toVisit{&_entry}; |
| 363 | std::set<CFG::BasicBlock const*> visited; |
| 364 | |
| 365 | // TODO: check whether visiting only a subset of these in the outer iteration below is enough. |
| 366 | std::list<std::pair<CFG::BasicBlock const*, CFG::BasicBlock const*>> backwardsJumps = collectBackwardsJumps(_entry); |
| 367 | |
| 368 | while (!toVisit.empty()) |
| 369 | { |
| 370 | // First calculate stack layouts without walking backwards jumps, i.e. assuming the current preliminary |
| 371 | // entry layout of the backwards jump target as the initial exit layout of the backwards-jumping block. |
| 372 | while (!toVisit.empty()) |
| 373 | { |
| 374 | CFG::BasicBlock const* block = *toVisit.begin(); |
| 375 | toVisit.pop_front(); |
| 376 | |
| 377 | if (visited.count(block)) |
| 378 | continue; |
| 379 | |
| 380 | if (std::optional<Stack> exitLayout = getExitLayoutOrStageDependencies(*block, visited, toVisit)) |
| 381 | { |
| 382 | visited.emplace(block); |
| 383 | auto& info = m_layout.blockInfos[block]; |
| 384 | info.exitLayout = *exitLayout; |
| 385 | info.entryLayout = propagateStackThroughBlock(info.exitLayout, *block); |
| 386 | |
| 387 | for (auto entry: block->entries) |
| 388 | toVisit.emplace_back(entry); |
| 389 | } |
| 390 | else |
| 391 | continue; |
| 392 | } |
| 393 | |
| 394 | // Determine which backwards jumps still require fixing and stage revisits of appropriate nodes. |
| 395 | for (auto [jumpingBlock, target]: backwardsJumps) |
| 396 | // This block jumps backwards, but does not provide all slots required by the jump target on exit. |
| 397 | // Therefore we need to visit the subgraph between ``target`` and ``jumpingBlock`` again. |
| 398 | if (ranges::any_of( |
| 399 | m_layout.blockInfos[target].entryLayout, |
| 400 | [exitLayout = m_layout.blockInfos[jumpingBlock].exitLayout](StackSlot const& _slot) { |
| 401 | return !util::contains(exitLayout, _slot); |
| 402 | } |
| 403 | )) |
| 404 | { |
| 405 | // In particular we can visit backwards starting from ``jumpingBlock`` and mark all entries to-be-visited- |
| 406 | // again until we hit ``target``. |
| 407 | toVisit.emplace_front(jumpingBlock); |
| 408 | // Since we are likely to permute the entry layout of ``target``, we also visit its entries again. |
| 409 | // This is not required for correctness, since the set of stack slots will match, but it may move some |
| 410 | // required stack shuffling from the loop condition to outside the loop. |
| 411 | for (CFG::BasicBlock const* entry: target->entries) |
| 412 | visited.erase(entry); |
| 413 | util::BreadthFirstSearch<CFG::BasicBlock const*>{{jumpingBlock}}.run( |
| 414 | [&visited, target = target](CFG::BasicBlock const* _block, auto _addChild) { |
| 415 | visited.erase(_block); |
| 416 | if (_block == target) |
| 417 | return; |