This file implements a CFG sorting pass. More...

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyExceptionInfo.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/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for WebAssemblyCFGSort.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE "wasm-cfg-sort"

Functions
	INITIALIZE_PASS (WebAssemblyCFGSort, DEBUG_TYPE, "Reorders blocks in topological order", false, false) FunctionPass *llvm

static void	MaybeUpdateTerminator (MachineBasicBlock *MBB)

static void	SortBlocks (MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, const MachineDominatorTree &MDT)
	Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not dominated by their header. More...

Detailed Description

This file implements a CFG sorting pass.

This pass reorders the blocks in a function to put them into topological order, ignoring loop backedges, and without any loop or exception being interrupted by a block not dominated by the its header, with special care to keep the order as similar as possible to the original order.

Definition in file WebAssemblyCFGSort.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "wasm-cfg-sort"

Definition at line 36 of file WebAssemblyCFGSort.cpp.

Function Documentation

◆ INITIALIZE_PASS()

INITIALIZE_PASS	(	WebAssemblyCFGSort	,
		DEBUG_TYPE	,
		"Reorders blocks in topological order"	,
		false	,
		false
	)

Definition at line 129 of file WebAssemblyCFGSort.cpp.

◆ MaybeUpdateTerminator()

static void MaybeUpdateTerminator ( MachineBasicBlock * MBB )

static

Definition at line 136 of file WebAssemblyCFGSort.cpp.

References assert(), B, llvm::MachineBasicBlock::getNumber(), llvm::MachineBasicBlock::isEHPad(), llvm::MachineBasicBlock::terminators(), and llvm::MachineBasicBlock::updateTerminator().

Referenced by SortBlocks().

◆ SortBlocks()

static void SortBlocks	(	MachineFunction &	MF,
		const MachineLoopInfo &	MLI,
		const WebAssemblyExceptionInfo &	WEI,
		const MachineDominatorTree &	MDT
	)

static

Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not dominated by their header.

TODO: There are many opportunities for improving the heuristics here. Explore them.

Definition at line 231 of file WebAssemblyCFGSort.cpp.

References assert(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::back(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::RegionBase< Tr >::contains(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count(), llvm::dbgs(), llvm::MachineDominatorTree::dominates(), E, llvm::SmallVectorBase::empty(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty(), llvm::MachineBasicBlock::front(), llvm::WebAssembly::getBottom(), llvm::MachineLoopInfo::getLoopFor(), llvm::MachineFunction::getName(), llvm::MachineBasicBlock::getNumber(), llvm::MachineFunction::getNumBlockIDs(), llvm::MachineFunction::getRegInfo(), llvm::RegionInfoBase< Tr >::getRegionFor(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::MachineRegisterInfo::invalidateLiveness(), LLVM_DEBUG, MaybeUpdateTerminator(), llvm::MachineBasicBlock::moveAfter(), N, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val(), llvm::MachineBasicBlock::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MachineFunction::RenumberBlocks(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size(), and llvm::MachineBasicBlock::successors().

Macros