63 #define DEBUG_TYPE "wasm-fix-irreducible-control-flow"
70 static BlockVector getSortedEntries(
const BlockSet &Entries) {
71 BlockVector SortedEntries(Entries.begin(), Entries.end());
74 auto ANum = A->getNumber();
75 auto BNum =
B->getNumber();
84 class ReachabilityGraph {
87 : Entry(Entry), Blocks(Blocks) {
90 for (
auto *
MBB : Blocks) {
103 auto I = Reachable.find(
From);
104 if (
I == Reachable.end())
106 return I->second.count(To);
111 const BlockSet &getLoopers()
const {
return Loopers; }
114 const BlockSet &getLoopEntries()
const {
return LoopEntries; }
118 assert(inRegion(LoopEntry));
119 auto I = LoopEnterers.find(LoopEntry);
120 assert(
I != LoopEnterers.end());
126 const BlockSet &Blocks;
128 BlockSet Loopers, LoopEntries;
139 using BlockPair = std::pair<MachineBasicBlock *, MachineBasicBlock *>;
143 for (
auto *
MBB : Blocks) {
145 if (Succ != Entry && inRegion(Succ)) {
152 while (!WorkList.empty()) {
155 assert(inRegion(
MBB) && Succ != Entry && inRegion(Succ));
160 if (Reachable[Pred].insert(Succ).second) {
168 for (
auto *
MBB : Blocks) {
173 assert(!Loopers.count(Entry));
177 for (
auto *Looper : Loopers) {
178 for (
auto *Pred : Looper->predecessors()) {
181 if (!canReach(Looper, Pred)) {
182 LoopEntries.insert(Looper);
183 LoopEnterers[Looper].
insert(Pred);
195 : Entry(Entry), Enterers(Enterers) {
199 BlockSet &getBlocks() {
return Blocks; }
203 const BlockSet &Enterers;
210 BlockVector WorkList;
211 BlockSet AddedToWorkList;
212 Blocks.insert(Entry);
213 for (
auto *Pred : Entry->predecessors()) {
214 if (!Enterers.count(Pred)) {
215 WorkList.push_back(Pred);
216 AddedToWorkList.insert(Pred);
220 while (!WorkList.empty()) {
221 auto *
MBB = WorkList.pop_back_val();
223 if (Blocks.insert(
MBB).second) {
225 if (AddedToWorkList.insert(Pred).second)
226 WorkList.push_back(Pred);
235 return "WebAssembly Fix Irreducible Control Flow";
243 void makeSingleEntryLoop(BlockSet &Entries, BlockSet &Blocks,
251 bool WebAssemblyFixIrreducibleControlFlow::processRegion(
253 bool Changed =
false;
257 ReachabilityGraph Graph(Entry, Blocks);
259 bool FoundIrreducibility =
false;
261 for (
auto *LoopEntry : getSortedEntries(Graph.getLoopEntries())) {
287 BlockSet MutualLoopEntries;
288 MutualLoopEntries.insert(LoopEntry);
289 for (
auto *OtherLoopEntry : Graph.getLoopEntries()) {
290 if (OtherLoopEntry != LoopEntry &&
291 Graph.canReach(LoopEntry, OtherLoopEntry) &&
292 Graph.canReach(OtherLoopEntry, LoopEntry)) {
293 MutualLoopEntries.insert(OtherLoopEntry);
297 if (MutualLoopEntries.size() > 1) {
298 makeSingleEntryLoop(MutualLoopEntries, Blocks, MF, Graph);
299 FoundIrreducibility =
true;
310 if (FoundIrreducibility) {
314 for (
auto *LoopEntry : Graph.getLoopEntries()) {
315 LoopBlocks InnerBlocks(LoopEntry, Graph.getLoopEnterers(LoopEntry));
322 if (processRegion(LoopEntry, InnerBlocks.getBlocks(), MF)) {
337 void WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop(
339 const ReachabilityGraph &Graph) {
340 assert(Entries.size() >= 2);
343 BlockVector SortedEntries = getSortedEntries(Entries);
346 for (
auto Block : SortedEntries)
347 assert(Block->getNumber() != -1);
348 if (SortedEntries.size() > 1) {
349 for (
auto I = SortedEntries.begin(),
E = SortedEntries.end() - 1;
I !=
E;
351 auto ANum = (*I)->getNumber();
352 auto BNum = (*(std::next(
I)))->getNumber();
361 Blocks.insert(Dispatch);
377 for (
auto *Entry : SortedEntries) {
378 auto Pair = Indices.
insert(std::make_pair(Entry, 0));
382 Pair.first->second =
Index;
392 BlockVector AllPreds;
393 for (
auto *Entry : SortedEntries) {
394 for (
auto *Pred : Entry->predecessors()) {
395 if (Pred != Dispatch) {
396 AllPreds.push_back(Pred);
403 for (
auto *Pred : AllPreds) {
404 for (
auto *Entry : Pred->successors()) {
405 if (!Entries.count(Entry))
407 if (Graph.canReach(Entry, Pred)) {
418 for (
auto *Pred : AllPreds) {
419 bool PredInLoop = InLoop.
count(Pred);
420 for (
auto *Entry : Pred->successors())
421 if (Entries.count(Entry) && Pred->isLayoutSuccessor(Entry))
422 EntryToLayoutPred[{Entry, PredInLoop}] = Pred;
431 for (
auto *Pred : AllPreds) {
432 bool PredInLoop = InLoop.
count(Pred);
433 for (
auto *Entry : Pred->successors()) {
434 if (!Entries.count(Entry) || Map.count({Entry, PredInLoop}))
439 if (
auto *OtherPred = EntryToLayoutPred.
lookup({Entry, PredInLoop}))
440 if (OtherPred != Pred)
445 MF.
insert(Pred->isLayoutSuccessor(Entry)
449 Blocks.insert(Routing);
457 Map[{Entry, PredInLoop}] = Routing;
461 for (
auto *Pred : AllPreds) {
462 bool PredInLoop = InLoop.
count(Pred);
465 for (
auto &
Op :
Term.explicit_uses())
466 if (
Op.isMBB() && Indices.
count(
Op.getMBB()))
467 Op.setMBB(Map[{
Op.getMBB(), PredInLoop}]);
469 for (
auto *Succ : Pred->successors()) {
470 if (!Entries.count(Succ))
472 auto *Routing = Map[{Succ, PredInLoop}];
473 Pred->replaceSuccessor(Succ, Routing);
487 "Removes irreducible control flow",
false,
false)
490 return new WebAssemblyFixIrreducibleControlFlow();
520 TII.get(WebAssembly::IMPLICIT_DEF),
Reg);
527 MI.removeFromParent();
528 Entry.insert(Entry.begin(), &
MI);
533 bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(
535 LLVM_DEBUG(
dbgs() <<
"********** Fixing Irreducible Control Flow **********\n"
536 "********** Function: "
541 for (
auto &
MBB : MF) {
542 AllBlocks.insert(&
MBB);
545 if (
LLVM_UNLIKELY(processRegion(&*MF.begin(), AllBlocks, MF))) {