[WebAssembly] Split CFG-sorting into its own pass. NFC.
CFG sorting was already an independent algorithm from block/loop insertion;
this change makes it more convenient to debug.
llvm-svn: 296399
diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
index cf094b9..bd11d1b4 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
@@ -10,12 +10,7 @@
/// \file
/// \brief This file implements a CFG stacking pass.
///
-/// This pass reorders the blocks in a function to put them into topological
-/// order, ignoring loop backedges, and without any loop being interrupted
-/// by a block not dominated by the loop header, with special care to keep the
-/// order as similar as possible to the original order.
-///
-/// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since
+/// This pass inserts BLOCK and LOOP markers to mark the start of scopes, since
/// scope boundaries serve as the labels for WebAssembly's control transfers.
///
/// This is sufficient to convert arbitrary CFGs into a form that works on
@@ -28,8 +23,6 @@
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySubtarget.h"
#include "WebAssemblyUtilities.h"
-#include "llvm/ADT/PriorityQueue.h"
-#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -68,217 +61,6 @@
return new WebAssemblyCFGStackify();
}
-/// Return the "bottom" block of a loop. This differs from
-/// MachineLoop::getBottomBlock in that it works even if the loop is
-/// discontiguous.
-static MachineBasicBlock *LoopBottom(const MachineLoop *Loop) {
- MachineBasicBlock *Bottom = Loop->getHeader();
- for (MachineBasicBlock *MBB : Loop->blocks())
- if (MBB->getNumber() > Bottom->getNumber())
- Bottom = MBB;
- return Bottom;
-}
-
-static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
-#ifndef NDEBUG
- bool AnyBarrier = false;
-#endif
- bool AllAnalyzable = true;
- for (const MachineInstr &Term : MBB->terminators()) {
-#ifndef NDEBUG
- AnyBarrier |= Term.isBarrier();
-#endif
- AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
- }
- assert((AnyBarrier || AllAnalyzable) &&
- "AnalyzeBranch needs to analyze any block with a fallthrough");
- if (AllAnalyzable)
- MBB->updateTerminator();
-}
-
-namespace {
-/// Sort blocks by their number.
-struct CompareBlockNumbers {
- bool operator()(const MachineBasicBlock *A,
- const MachineBasicBlock *B) const {
- return A->getNumber() > B->getNumber();
- }
-};
-/// Sort blocks by their number in the opposite order..
-struct CompareBlockNumbersBackwards {
- bool operator()(const MachineBasicBlock *A,
- const MachineBasicBlock *B) const {
- return A->getNumber() < B->getNumber();
- }
-};
-/// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
-/// by the loop header among the loop's blocks.
-struct Entry {
- const MachineLoop *Loop;
- unsigned NumBlocksLeft;
-
- /// List of blocks not dominated by Loop's header that are deferred until
- /// after all of Loop's blocks have been seen.
- std::vector<MachineBasicBlock *> Deferred;
-
- explicit Entry(const MachineLoop *L)
- : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
-};
-}
-
-/// Sort the blocks, taking special care to make sure that loops are not
-/// interrupted by blocks not dominated by their header.
-/// TODO: There are many opportunities for improving the heuristics here.
-/// Explore them.
-static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
- const MachineDominatorTree &MDT) {
- // Prepare for a topological sort: Record the number of predecessors each
- // block has, ignoring loop backedges.
- MF.RenumberBlocks();
- SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
- for (MachineBasicBlock &MBB : MF) {
- unsigned N = MBB.pred_size();
- if (MachineLoop *L = MLI.getLoopFor(&MBB))
- if (L->getHeader() == &MBB)
- for (const MachineBasicBlock *Pred : MBB.predecessors())
- if (L->contains(Pred))
- --N;
- NumPredsLeft[MBB.getNumber()] = N;
- }
-
- // Topological sort the CFG, with additional constraints:
- // - Between a loop header and the last block in the loop, there can be
- // no blocks not dominated by the loop header.
- // - It's desirable to preserve the original block order when possible.
- // We use two ready lists; Preferred and Ready. Preferred has recently
- // processed sucessors, to help preserve block sequences from the original
- // order. Ready has the remaining ready blocks.
- PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
- CompareBlockNumbers>
- Preferred;
- PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
- CompareBlockNumbersBackwards>
- Ready;
- SmallVector<Entry, 4> Loops;
- for (MachineBasicBlock *MBB = &MF.front();;) {
- const MachineLoop *L = MLI.getLoopFor(MBB);
- if (L) {
- // If MBB is a loop header, add it to the active loop list. We can't put
- // any blocks that it doesn't dominate until we see the end of the loop.
- if (L->getHeader() == MBB)
- Loops.push_back(Entry(L));
- // For each active loop the block is in, decrement the count. If MBB is
- // the last block in an active loop, take it off the list and pick up any
- // blocks deferred because the header didn't dominate them.
- for (Entry &E : Loops)
- if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
- for (auto DeferredBlock : E.Deferred)
- Ready.push(DeferredBlock);
- while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
- Loops.pop_back();
- }
- // The main topological sort logic.
- for (MachineBasicBlock *Succ : MBB->successors()) {
- // Ignore backedges.
- if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
- if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
- continue;
- // Decrement the predecessor count. If it's now zero, it's ready.
- if (--NumPredsLeft[Succ->getNumber()] == 0)
- Preferred.push(Succ);
- }
- // Determine the block to follow MBB. First try to find a preferred block,
- // to preserve the original block order when possible.
- MachineBasicBlock *Next = nullptr;
- while (!Preferred.empty()) {
- Next = Preferred.top();
- Preferred.pop();
- // If X isn't dominated by the top active loop header, defer it until that
- // loop is done.
- if (!Loops.empty() &&
- !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
- Loops.back().Deferred.push_back(Next);
- Next = nullptr;
- continue;
- }
- // If Next was originally ordered before MBB, and it isn't because it was
- // loop-rotated above the header, it's not preferred.
- if (Next->getNumber() < MBB->getNumber() &&
- (!L || !L->contains(Next) ||
- L->getHeader()->getNumber() < Next->getNumber())) {
- Ready.push(Next);
- Next = nullptr;
- continue;
- }
- break;
- }
- // If we didn't find a suitable block in the Preferred list, check the
- // general Ready list.
- if (!Next) {
- // If there are no more blocks to process, we're done.
- if (Ready.empty()) {
- MaybeUpdateTerminator(MBB);
- break;
- }
- for (;;) {
- Next = Ready.top();
- Ready.pop();
- // If Next isn't dominated by the top active loop header, defer it until
- // that loop is done.
- if (!Loops.empty() &&
- !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
- Loops.back().Deferred.push_back(Next);
- continue;
- }
- break;
- }
- }
- // Move the next block into place and iterate.
- Next->moveAfter(MBB);
- MaybeUpdateTerminator(MBB);
- MBB = Next;
- }
- assert(Loops.empty() && "Active loop list not finished");
- MF.RenumberBlocks();
-
-#ifndef NDEBUG
- SmallSetVector<MachineLoop *, 8> OnStack;
-
- // Insert a sentinel representing the degenerate loop that starts at the
- // function entry block and includes the entire function as a "loop" that
- // executes once.
- OnStack.insert(nullptr);
-
- for (auto &MBB : MF) {
- assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
-
- MachineLoop *Loop = MLI.getLoopFor(&MBB);
- if (Loop && &MBB == Loop->getHeader()) {
- // Loop header. The loop predecessor should be sorted above, and the other
- // predecessors should be backedges below.
- for (auto Pred : MBB.predecessors())
- assert(
- (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
- "Loop header predecessors must be loop predecessors or backedges");
- assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
- } else {
- // Not a loop header. All predecessors should be sorted above.
- for (auto Pred : MBB.predecessors())
- assert(Pred->getNumber() < MBB.getNumber() &&
- "Non-loop-header predecessors should be topologically sorted");
- assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
- "Blocks must be nested in their loops");
- }
- while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
- OnStack.pop_back();
- }
- assert(OnStack.pop_back_val() == nullptr &&
- "The function entry block shouldn't actually be a loop header");
- assert(OnStack.empty() &&
- "Control flow stack pushes and pops should be balanced.");
-#endif
-}
-
/// Test whether Pred has any terminators explicitly branching to MBB, as
/// opposed to falling through. Note that it's possible (eg. in unoptimized
/// code) for a branch instruction to both branch to a block and fallthrough
@@ -583,9 +365,6 @@
WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
MF.getRegInfo().invalidateLiveness();
- // Sort the blocks, with contiguous loops.
- SortBlocks(MF, MLI, MDT);
-
// Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
PlaceMarkers(MF, MLI, TII, MDT, MFI);