LLVM  7.0.0svn
Macros | Functions
WebAssemblyFixIrreducibleControlFlow.cpp File Reference

This file implements a pass that transforms irreducible control flow into reducible control flow. More...

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySubtarget.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.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 WebAssemblyFixIrreducibleControlFlow.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "wasm-fix-irreducible-control-flow"
 

Functions

 INITIALIZE_PASS (WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE, "Removes irreducible control flow", false, false) FunctionPass *llvm
 

Detailed Description

This file implements a pass that transforms irreducible control flow into reducible control flow.

Irreducible control flow means multiple-entry loops; they appear as CFG cycles that are not recorded in MachineLoopInfo due to being unnatural.

Note that LLVM has a generic pass that lowers irreducible control flow, but it linearizes control flow, turning diamonds into two triangles, which is both unnecessary and undesirable for WebAssembly.

TODO: The transformation implemented here handles all irreducible control flow, without exponential code-size expansion, though it does so by creating inefficient code in many cases. Ideally, we should add other transformations, including code-duplicating cases, which can be more efficient in common cases, and they can fall back to this conservative implementation as needed.

Definition in file WebAssemblyFixIrreducibleControlFlow.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "wasm-fix-irreducible-control-flow"

Definition at line 46 of file WebAssemblyFixIrreducibleControlFlow.cpp.

Function Documentation

◆ INITIALIZE_PASS()

INITIALIZE_PASS ( WebAssemblyFixIrreducibleControlFlow  ,
DEBUG_TYPE  ,
"Removes irreducible control flow"  ,
false  ,
false   
)

Definition at line 74 of file WebAssemblyFixIrreducibleControlFlow.cpp.

References llvm::MachineInstrBuilder::addMBB(), llvm::MachineInstrBuilder::addReg(), llvm::MachineBasicBlock::addSuccessor(), assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SetVector< T, Vector, Set >::begin(), llvm::MachineLoopInfo::begin(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::MachineFunction::begin(), llvm::ISD::BR, llvm::BuildMI(), llvm::MachineLoopInfo::changeLoopFor(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::MachineFunction::CreateMachineBasicBlock(), llvm::dbgs(), llvm::SmallVectorBase::empty(), llvm::SetVector< T, Vector, Set >::empty(), llvm::SetVector< T, Vector, Set >::end(), llvm::MachineLoopInfo::end(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::MachineBasicBlock::end(), llvm::MachineFunction::end(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::LoopBase< BlockT, LoopT >::getExitBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::MachineInstrBuilder::getInstr(), llvm::MachineLoopInfo::getLoopFor(), llvm::MachineFunction::getName(), llvm::MachineInstr::getNumExplicitOperands(), llvm::MachineInstr::getOperand(), llvm::MachineFunction::getRegInfo(), llvm::MachineFunction::getSubtarget(), llvm::SetVector< T, Vector, Set >::insert(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::MachineFunction::insert(), llvm::MachineRegisterInfo::invalidateLiveness(), LLVM_DEBUG, LLVM_LIKELY, LLVM_UNLIKELY, MRI, llvm::operator!=(), llvm::operator==(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::pop_back(), llvm::MachineBasicBlock::pred_begin(), llvm::MachineBasicBlock::pred_end(), llvm::predecessors(), llvm::MachineBasicBlock::predecessors(), llvm::printMBBReference(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), Reg, llvm::MachineFunction::RenumberBlocks(), llvm::MachineLoopInfo::runOnMachineFunction(), llvm::size(), Split(), llvm::MachineBasicBlock::succ_begin(), llvm::MachineBasicBlock::succ_end(), llvm::successors(), and TII.